Product of polynomials modulo 2 in integer representation

Your task is to implements the product of polynomials modulo 2 $({\mathbb{F}}_2[x]$) in integer representation.

Background

The field ${\mathbb{F}}_2$ represents the integers modulo 2, or equivalently, the lowest bit of the binary representation of an integer; it only has the values $0$ and $1$. What I mean with a polynomial modulo 2 (note that this might not be the correct mathematical term) is a polynomial with coefficients from ${\mathbb{F}}_2$. Since the coefficients can only be $0$ or $1$, such a polynomial is just a sum of terms of the form $x^n$, for example $x^5+x^2+1$.

Multiplying of polynomials modulo 2 can be done by doing normal polynomial multiplication, dropping all terms with even coefficient from the resulting polynomial, and then removing the (odd) factors from the remaining terms.

Now since the coefficients are all either 0 or 1, they can be represented as bits of a (non-negative) integer. To get the integer representation of the polynomial, just interpret it as normal polynomial and evaluate it at $x=2$, for example, the polynomial $x^4+x^3+x$ is represented by the number $2^4+2^3+2=26$. For the reverse direction, just represent the number in binary, and read off the coefficients: $26={11010}_2$ represents the polynomial $1x^4+1x^3+0x^2+1x+0=x^4+x^3+x$

Task

Your task is to write a function that takes two non-negative integers, interprets them as polynomials modulo 2, and returns the integer representing their product.

Your program must handle at least products of polynomials up to degree 14, or equivalently, input numbers from $0$ to $32767$ inclusive.

Error handling for invalid input (negative numbers, or non-integers in languages that don't do static typing) is not required.

Scoring

This is code golf, the shortest entry wins.

Example code

Here is an implementation in Python (not golfed) that you can use to compare your results to:

def polymul_mod2(m, n):
    m_digits = [int(d) for d in bin(m)[:1:-1]]
    n_digits = [int(d) for d in bin(n)[:1:-1]]
    m_len = len(m_digits)
    n_len = len(n_digits)
    p_len = m_len + n_len
    polyprod_digits = [0] * p_len
    for i in range(m_len):
        for k in range(n_len):
            polyprod_digits[i + k] += m_digits[i] * n_digits[k]
    return sum(2**k * (polyprod_digits[k] % 2) for k in range(p_len))

Test cases

The following test cases first give the two factors, separated by x, and then the result, separated by =.

0 x 0 = 0
0 x 1 = 0
1 x 1 = 1
2 x 1 = 2
2 x 2 = 4
3 x 2 = 6
3 x 3 = 5
6 x 7 = 18
7 x 6 = 18
8 x 5 = 40
11 x 10 = 78
25 x 15 = 135
26 x 15 = 150
32767 x 32767 = 357913941

posted 6 months ago

CC BY-SA 4.0

6mo ago

celtschk‭

1414 reputation 28 50 181 74