...
We define that a polynomial X is greater than or equal to polynomial Y if and only if the highest set bit of X is the same or greater than the position of the highest set bit in Y.
Example
Consider the following:
...
| Code Block | ||||
|---|---|---|---|---|
| ||||
a * b = a_0 + a_1 + ... + a_b = b_0 + b_1 + ... + b_a |
where + is the polynomial addition operator.
...
| Code Block | ||||
|---|---|---|---|---|
| ||||
1000
x 1011
---------
1000 (D0 of 1011 is 1)
1000. (D1 of 1011 is 1)
0000.. (D2 of 1011 is 0)
+ 1000... (D3 of 1011 is 1)
-----------
1011000
--------- |
Polynomial Division
Polynomial division is very similar to long division. The only difference is that we use our definition of "greater than or equal to" for polynomials, and we perform subtraction under polynomial arithmetic instead.
...
We say that a polynomial AX is a multiple of polynomial B Y under polynomial arithmetic, if and only if it is possible to construct polynomial A X by XORing in various shifts of B. This implies that Y. Moreover, a polynomial A X is not a multiple of polynomial B Y if and only if it is not possible to construct polynomial A X by XORing various shifts of polynomial Bof polynomial Y.