The Polynomial Ring over $\mathbb{R}$

In abstract algebra a ring is a set $R$ together with a "+" operation and a "$\times$" operation.

The main example of a ring is a space of polynomials with coefficients in $\mathbb{R}$.

We all know that these polynomials can be added and multiplied.

For example if $p = x^3+x^2 + 1$ and $q = x^2+x$ then you can add $p$ and $q$:

You can also multiply polynomials and the result is another polynomial:

Polynomials also "distribute" the same way numbers do. If $p,q,$ and $s$ are polynomials, then

We call algebraic structures that support these operations rings.

The integers are also a ring.

--

In many ways polynomials are a lot like integers.

• Like integers, every polynomial $p$ has a "negative" $-p$ and $p+(-p) = 0$.

• Like integers, addition and multiplication on polynomials is commutative and associative:

(Commutativity)

$pq = qp$

and

(Associativity)

$p(qs) = (pq)s$

• Like integers, you can multiply polynomials, but polynomials do not have "reciprocals".

(No inverses)

Just as $\frac{1}{2}$, the inverse of 2, is not an integer, there is similarly no polynomial $p^{-1}$ such that $pp^{-1} = 1$.

Division theorem

Polynomials and integers are so similar that you can prove some of the same theorems about both.

The division theorem for example depends only on properties that integers and polynomials have in common.

Integer division theorem

For all integers $n$, $m$ there are integers $q$ and $r$ (with $0 \leq r < m$) such that

Polynomial division theorem

For all polynomials $p$ and $s$ there are polynomials $q$ and $r$ (with $0 \leq deg($r$) < deg($s$)$) such that

Long division

The "proof" of the division theorem in the case of either integers or polynomials is what we call long division.

Long division is basically an algorithm for computing $q$ and $r$.

Polynomials with other kinds of coefficients

We saw that polynomials with coefficients in $\mathbb{R}$ form a ring.

The same thing is true when the coefficients come not from $\mathbb{R}$ but from $\mathbb{Z}_2$.

In this case

and

Nice properties

You can easily check that we still have all the nice properties as before:

Associativity: $(pq)s = p(qs)$

Commutativity: $pq = qp$ (Rings don't actually need to have commutative multiplication.)

Distributivity: $p(q+s) = pq + ps$.

Negatives: ??

Actually now each polynomial is it's own negative:

$p + p = 2p \equiv 0$.

Factoring

Everyone in college has some experience factoring polynomials.

For example, $x^2-4 = (x+2)(x-2)$.

On the other hand you might know that some polynomials "don't factor".

For example $p(x) = x^2 + 1$ has no real roots and no linear factors.

At least it doesn't have them over the real numbers.

This means that you can't write $p$ as the product of lower degree polynomials with real coefficients.

$\mathbb{C}$

On the other hand, every college student also knows that over the complex numbers all polynomials factor into linear polynomials.

$p(x) = x^2 + 1 = (x+i)(x-i)$, where $i = \sqrt{-1}$.

Modern algebra

This gives you some important insight:

Whether a polynomial factors depends on what coefficients you are allowed to use

The $\mathbb{Z}_2$ case

Let's use Sage to look at some polynomials with coefficients in $\mathbb{Z}_2$ and see if they factor.

That is:

Does the polynomial factor into a product of lower degree polynomials with coefficients in $\mathbb{Z}_2$?

Irreducible polynomials

We say that a polynomial which does not factor into lower degree polynomials (with coefficients in $\mathbb{Z}_2$) is irreducible.

You can see from the above output that unlike polynomials over $\mathbb{R}$, there can be irreducible polynomials of degree higher than 2.

In fact there are irreducible polynomials of every degree over $\mathbb{Z}_2$.

Irreducible polynomials are a lot like prime numbers.

Mod out

In fact irreducible polynomials are so much like prime numbers that you can quotient out by them to make interesting algebraic structures.

To see the analogy remember this:

Two integers $m$ and $n$ are equivalent modulo $p\in \mathbb{Z}$ if when you apply the division theorem,

and $r_m = r_n$ (with $0\leq r_n < q_n$ and $0 \leq r_m < q_m$).

If $p$ is prime then the resulting algebraic structure $\mathbb{Z}_p$ is a field.

This means that inverses exist for every nonzero element.

(Remember that $a$ has an inverse mod $n$ iff $\gcd(a,n)=1$. But if $n$ is prime, this is always true if $a \neq 0$.)

Polynomial version

Two polynomials with coefficients in $\mathbb{Z}_2$ $m$ and $n$ are equivalent modulo $p$ (where $p$ also has coefficients in $\mathbb{Z}_2$) if when you apply the division theorem,

and $r_m = r_n$ (with $0\leq \deg(r_n) < \deg(q_n)$ and $0 \leq \deg(r_m) < \deg(q_m)$).

If $p$ is irreducible then the resulting algebraic structure is a field.

This means that multiplicative inverses exist for every nonzero polynomial.

The form of this algebraic structure depends only on the degree $d$ of $p$.

That is, any other irreducible $p$ of the same degree would produce essentially the same system.

The notation for this algebraic structure is $GF(2^d)$.

This is read "The Galois field of order $2^d$."

There are exactly $2^d$ equivalence classes.

Let's do a Sage example!

Some observations

Let's make some observations about this field:

1. There are indeed exactly $2^4 = 16$ elements.

2. The elements are precisely the polynomials of degree less than $d=4$ with coefficients in $\mathbb{Z}_2$.

3. These are exactly the possible remainders when you divide a polynomial with coefficients in $\mathbb{Z}_2$ by $p(x) = x^4 + x^3 + x^2 + x + 1$.

Why are there no elements of degree higher than 3?

The reason is that if $s$ has degree 4 or more, then when $p(x) = x^4 + x^3 + x^2 + x + 1$ divides it the remainder has degree at most three.

Therefore every polynomial with coefficients in $\mathbb{Z}_2$ is equivalent,modulo $p$, to some polynomial of degree less than four with coefficients in $\mathbb{Z}_2$.

An interesting exercise is to look at the "powers of $x$".

This is often used in cryptography, for example in the AES key schedule and in XTS-AES block cipher mode.

Exercise

Do the reduction $x^4 \equiv x^3 + x^2 + x+ 1 \mod x^4 + x^3 + x^2 + x + 1$ by hand.

Solution:

Since $p(x) = x^4 + x^3 + x^2 + x + 1 \equiv 0$, it follows that $x^3 + x^2 + x + 1 \equiv x^4$.

Modding out by $x^4+x+1$

The book explores the field $GF(2^4)$ but with the irreducible polynomial $p(x)=x^4+x+1$.

Some similarities and differences

This field is essentially the same a the last one.

But different elements play different "roles".

For instance in this field, powers of $x$ generate all of the nonzero elements.

Addition in $GF(16)$

Because addition does not increase the degree, addition in GF(16) is basically the same as in the ring of polynomials with coefficients in $\mathbb{Z}_2$.

For example:

$(x^3+x^2+1) + (x^3+x^2) \equiv x^3 + 1$.

You could be a stickler and say what we really care about is not $x^3 + 1$ but rather the remainder when it is divided by $x^4+x+1$.

However because the degree is 3<4, the remainder is just $x^3+1$ itself.

Multiplication in $GF(16)$

Because all polynomials must have degree at most 3, multiplication in $GF(16)$ is much different than in the polynomial ring over $\mathbb{Z}_2$.

That's because multiplication does increase the degree.

For example in the ring $\mathbb{Z}_2[x]$ of polynomials over $\mathbb{Z}_2$,

$(x^3+x^2+1) \cdot (x^3+x^2) = x^6+x^5+x^5+x^4+x^3+x^2 \equiv x^6 + x^4 + x^3 +x^2$.

However we are not interested directly in $x^6 + x^4 + x^3 +x^2$ but rather its remainder when we divide it by $x^4+x+1$.

We can use Sage to compute the remainder:

Note that if we compute the product of the polynomials in the field, we get exactly this result.

Funny Arithmetic over Nybbles

We said that $GF(2^4)$ is exactly the polynomials with coefficients in $\mathbb{Z}_2$ with degree less than 4.

More generally, $GF(2^d)$ is exactly the polynomials with coefficients in $\mathbb{Z}_2$ with degree less than $d$.

We can associate polynomials over $\mathbb{Z}_2$ with binary numbers by only remembering the coefficients.

The rule is:

$c_{d-1}x^{d-1} + c_{d-2}x^{d-2} + \cdots + c_1x + c_0 \mapsto c_{d-1}c_{d-2}\cdots c_1 c_ 0$.

For example

$x^3 + x^2 + 1 \mapsto 1101$

and

$x^3 + x^2 \mapsto 1100$

and

$0 \mapsto 0000$

etc.

This means that $GF(16)$ exactly corresponds to nybbles (half bytes) or equivalently to the hexadecimal digits.

Here it is in Sage.

Funny arithmetic, cont.

To someone who couldn't "see" the polynomials, but only their corresponding digits, it would look like a funny kind of arithmetic is going on.

For example the fact that

$(x^3+x^2+1) + (x^3+x^2) \equiv x^3 + 1$.

would look like

$d + c = 9$.

And the fact that

$(x^3+x^2+1) \cdot (x^3+x^2) = x^6+x^5+x^5+x^4+x^3+x^2 \equiv x^6 + x^4 + x^3 +x^2 \equiv x+1 (\mod x^4+x+1)$

would look like

$d\cdot c = 3$.

We could in fact make a whole crazy multiplication table that would look a little like this:

Funny arithmetic on bytes

We could do the same thing with bytes rather than nybbles.

We just need a bigger field.

This field also has a multiplication table, but now it is size 256x256, which is too big to print out.

Nevertheless, we have our funny math on bytes.

For example the work below shows that

$0x66 \times 0xaf = 0x8b.$

Wait...why are we using a field?

So far we have not made any use of inverses.

We have been using $GF(2^d)$ just as if it were a finite ring (which it also is).

But it turns out that one of the best uses of $GF(2^d)$ is to use the inverse operation as a kind of substitution.

If we call this substitution operation, $S$ then

This turns out to be highly nonlinear.

In cryptography we love non-linear substitutions because they defeat differential cryptanalysis.

Being non-linear in this case means that

$S(p\cdot q) \neq S(p)\cdot S(q).$

We will see later that we also need to tweak this idea a bit to prevent algebraic attacks.

But using inverses for substitutions is an important idea for the AES S-box or substitution box.

We will come back to this when we visit AES in detail.

For now, we use Sage to produce a table of inverses.

Other finite fields

So far we have explored only finite fields of the form $GF(2^d)$.

These are the finite fields most important to cryptgraphy.

However we are close to a beautiful theorem, so we will state it for your general edification:

Theorem:

For every prime $p$ and every counting number $d$ there is a unique (up to isomorphism) field of cardinality $p^d$ (denoted $GF(p^d)$). There are no other finite fields.

You know what $GF(2^d)$ is: polynomials over $\mathbb{Z}_2$ modulo some polynomial $P$ which is irreducible over $\mathbb{Z}_2$ and $\deg(P)=d$..

More generally, for any prime $p$,

$GF(p^d)$ is: polynomials over $\mathbb{Z}_p$ modulo some polynomial $P$ which is irreducible over $\mathbb{Z}_p$ and $\deg(P)=d$.

This idea makes sense even when $d=1$, but we usually write $\mathbb{Z}_p$ rather than $GF(p)$ (at least in this class).