2
$\begingroup$

In the carryless multiplication of two polynomials in a 8-bit environment, is it possible to obtain the original 8-bit values from the result?

As an example:

$$\begin{align} (x^{11} + x^{10} + x^9 ) + (x^7 + x^5 + x^4 + x^3 + x^1) &= (x^6 + x^5 + x^1) \times (x^5 + x^3 + x^2 + x^0)\\ (x^{11} + x^{10}) + (x^6 + x^4 + x^2 + x^1) &= \text?\times\text?\quad \hbox{(each value must fit in 8 bits)} \end{align}$$

I know that I can try every possible value (it's only two 8-bit values) but that seems blunt!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.