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.
Example
Take the polynomials $x^4 + x^3 + x$ and $x^3 + x^2 + x + 1$. The normal product of those is $$(x^4 +x^3 + x)(x^3 + x^2 + x +1) = x^7 + 2x^6 + 2x^5 + 3x^4 + 2x^3 + x^2 + x.$$ The terms with $x^6$, $x^5$ and $x^3$ have even coefficients and therefore are dropped, and for $x^4$ the odd coefficient is dropped, and therefore the product of those polynomials modulo 2 is $$x^7 + x^4 + x^2 + x$$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
0 comment threads