The Polynomial Ring over
In abstract algebra a ring is a set together with a "+" operation and a "" operation.
The main example of a ring is a space of polynomials with coefficients in .
We all know that these polynomials can be added and multiplied.
For example if and then you can add and :
You can also multiply polynomials and the result is another polynomial:
Polynomials also "distribute" the same way numbers do. If and 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 has a "negative" and .
Like integers, addition and multiplication on polynomials is commutative and associative:
(Commutativity)
and
(Associativity)
Like integers, you can multiply polynomials, but polynomials do not have "reciprocals".
(No inverses)
Just as , the inverse of 2, is not an integer, there is similarly no polynomial such that .
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 , there are integers and (with ) such that
For all polynomials and there are polynomials and (with rs) 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 and .
Polynomials with other kinds of coefficients
We saw that polynomials with coefficients in form a ring.
The same thing is true when the coefficients come not from but from .
In this case
and
Nice properties
You can easily check that we still have all the nice properties as before:
Associativity:
Commutativity: (Rings don't actually need to have commutative multiplication.)
Distributivity: .
Negatives: ??
Actually now each polynomial is it's own negative:
.
Factoring
Everyone in college has some experience factoring polynomials.
For example, .
On the other hand you might know that some polynomials "don't factor".
For example 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 as the product of lower degree polynomials with real coefficients.
On the other hand, every college student also knows that over the complex numbers all polynomials factor into linear polynomials.
, where .
Modern algebra
This gives you some important insight:
Whether a polynomial factors depends on what coefficients you are allowed to use
The case
Let's use Sage to look at some polynomials with coefficients in and see if they factor.
That is:
Does the polynomial factor into a product of lower degree polynomials with coefficients in ?
Irreducible polynomials
We say that a polynomial which does not factor into lower degree polynomials (with coefficients in ) is irreducible.
You can see from the above output that unlike polynomials over , there can be irreducible polynomials of degree higher than 2.
In fact there are irreducible polynomials of every degree over .
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 and are equivalent modulo if when you apply the division theorem,
and (with and ).
If is prime then the resulting algebraic structure is a field.
This means that inverses exist for every nonzero element.
(Remember that has an inverse mod iff . But if is prime, this is always true if .)
Polynomial version
Two polynomials with coefficients in and are equivalent modulo (where also has coefficients in ) if when you apply the division theorem,
and (with and ).
If 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 of .
That is, any other irreducible of the same degree would produce essentially the same system.
The notation for this algebraic structure is .
This is read "The Galois field of order ."
There are exactly equivalence classes.
Let's do a Sage example!
Some observations
Let's make some observations about this field:
There are indeed exactly elements.
The elements are precisely the polynomials of degree less than with coefficients in .
These are exactly the possible remainders when you divide a polynomial with coefficients in by .
Why are there no elements of degree higher than 3?
The reason is that if has degree 4 or more, then when divides it the remainder has degree at most three.
Therefore every polynomial with coefficients in is equivalent,modulo , to some polynomial of degree less than four with coefficients in .
An interesting exercise is to look at the "powers of ".
This is often used in cryptography, for example in the AES key schedule and in XTS-AES block cipher mode.
Exercise
Do the reduction by hand.
Solution:
Since , it follows that .
Modding out by
The book explores the field but with the irreducible polynomial .
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 generate all of the nonzero elements.
Addition in
Because addition does not increase the degree, addition in GF(16) is basically the same as in the ring of polynomials with coefficients in .
For example:
.
You could be a stickler and say what we really care about is not but rather the remainder when it is divided by .
However because the degree is 3<4, the remainder is just itself.
Multiplication in
Because all polynomials must have degree at most 3, multiplication in is much different than in the polynomial ring over .
That's because multiplication does increase the degree.
For example in the ring of polynomials over ,
.
However we are not interested directly in but rather its remainder when we divide it by .
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 is exactly the polynomials with coefficients in with degree less than 4.
More generally, is exactly the polynomials with coefficients in with degree less than .
We can associate polynomials over with binary numbers by only remembering the coefficients.
The rule is:
.
For example
and
and
etc.
This means that 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
.
would look like
.
And the fact that
would look like
.
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
Wait...why are we using a field?
So far we have not made any use of inverses.
We have been using just as if it were a finite ring (which it also is).
But it turns out that one of the best uses of is to use the inverse operation as a kind of substitution.
If we call this substitution operation, 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
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 .
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 and every counting number there is a unique (up to isomorphism) field of cardinality (denoted ). There are no other finite fields.
You know what is: polynomials over modulo some polynomial which is irreducible over and ..
More generally, for any prime ,
is: polynomials over modulo some polynomial which is irreducible over and .
This idea makes sense even when , but we usually write rather than (at least in this class).