Cheap and Secure Web Hosting Provider : See Now

# [Answers] How to revert a carryless polynomial multiplication?

, ,
Problem Detail:

In the carryless multiplication of two polynomials in a 8bit environment.

Is it possible to obtain the original 8bit values from the result?

As an example: (x11 + x10 + x9 ) + (x7 + x5 + x4 + x3 + x1) = (x6 + x5 + x1) * (x5 + x3 + x2 + x0)

(x11 + x10) + (x6 + x4 + x2 + x1) = ? * ? (each value must fit in 8 bit)

I know that i can try every possible value (its only two 8bit values) but that seems blunt!

###### Asked By : Filipe Almeida

Yes, there are efficient algorithms for this. All you need to do is factor the resulting polynomial, but taking all coefficients modulo 2. This is known as polynomial factorization in the field \$GF(2)\$. There are standard algorithms for polynomial factorization, and they are quite efficient. For instance, you could look at Sage or another mathematical computation toolkit; it's likely to have an existing implementation of those algorithms.

Note that after you've factored the polynomial, there may still be some ambiguity about what the original two polynomials were. For instance, if you are given the polynomial \$x^5+x^3\$, the two polynomials might be \$x^2+1\$ and \$x^3\$, or they might be \$x^3+x\$ and \$x^2\$, etc. You won't be able to tell, given just the product.