Polynomial Arithmetic

tags: math, cryptography

The reason we had to use polynomial arithmetic instead of normal Finite Fields, is due to the residuals need to be relatively prime to the field’s order, and to satisfy that we sometimes use number that don’t completely utilize bit representation.

Using Polynomial arithmetic modulo $m(x)$ of order n, solves this. We had to specially use modulo operations to solve the issues we faced earlier in past arithmetic groups like reversibility.

Irreducible Polynomials

They’re polynomials that act like prime numbers, they can not be expressed as a product of two polynomials.

Doing polynomial arithmetic in $GF(P^n)$

means the coefficient numbers are in $Z_p$ and the polynomials arithmetic operations are done with modulo $mod(x)$ of order n

All algorithms can be used and applied here like Eucledian and Extended Eucledian

Multiplication in $GF(2^8)$

First we are choosing $m(x)$ as the irreducible polynomial $x^8+x^4+x^3+x+1$, Now $x^{8}modm(x)$ is $x^4+x^3+x+1$

So multiplying a polynomial with order 7 by $x$ will either make it of order 8 or order 7 if the coefficient of $x^7$ was 0, this will only lead to a shift left without any reduction. If the coefficient was 1, then reduction is required, but only the $x^8$ will be reduced to the polynomial mentioned above which is equivalent to xoring it $00011011$.

The proof is in the reference page 137.