CoCalc Public FilesCrypto_Fall_20 / polyring / poly.sagewsOpen with one click!
Author: Hunter Johnson
Views : 52
License: GNU General Public License v3.0
Compute Environment: Ubuntu 20.04 (Default)

The Polynomial Ring over R\mathbb{R}

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

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

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

For example if p=x3+x2+1p = x^3+x^2 + 1 and q=x2+xq = x^2+x then you can add pp and qq:

p+q=(x3+x2+1)+(x2+x)=x3+2x2+x+1p + q = (x^3+x^2+1) + (x^2+x) = x^3 + 2x^2 +x + 1

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

pq=(x3+x2+1)(x2+x)=x5+x4+2x3+x2+x.p\cdot q = (x^3+x^2+1)(x^2+x) = x^5+x^4+2x^3+x^2+x.

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

p(q+s)=pq+ps.p(q+s) = pq + ps.

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 pp has a "negative" p-p and p+(p)=0p+(-p) = 0.
  • Like integers, addition and multiplication on polynomials is commutative and associative:
(Commutativity)

pq=qppq = qp

and

(Associativity)

p(qs)=(pq)sp(qs) = (pq)s

  • Like integers, you can multiply polynomials, but polynomials do not have "reciprocals".
(No inverses)

Just as 12\frac{1}{2}, the inverse of 2, is not an integer, there is similarly no polynomial p1p^{-1} such that pp1=1pp^{-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 nn, mm there are integers qq and rr (with 0r<m0 \leq r < m) such that

n=qm+r n = qm + r

Polynomial division theorem

For all polynomials pp and ss there are polynomials qq and rr (with 0deg(0 \leq deg(r)<deg() < deg(s))) such that

p=qs+r p = qs + r


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 qq and rr.

Polynomials with other kinds of coefficients

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

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

In this case

p+q=(x3+x2+1)+(x2+x)=x3+2x2+x+1x3+x+1.p + q = (x^3+x^2+1) + (x^2+x) = x^3 + 2x^2 +x + 1 \equiv x^3+x+1.

and

pq=(x3+x2+1)(x2+x)=x5+x4+2x3+x2+xx5+x4+x2+x.p\cdot q = (x^3+x^2+1)(x^2+x) = x^5+x^4+2x^3+x^2+x \equiv x^5+x^4+x^2+x.

Nice properties

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

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

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

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

Negatives: ??

Actually now each polynomial is it's own negative:

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

Factoring

Everyone in college has some experience factoring polynomials.

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

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

For example p(x)=x2+1p(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 pp as the product of lower degree polynomials with real coefficients.

C\mathbb{C}

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

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

Modern algebra

This gives you some important insight:

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

The Z2\mathbb{Z}_2 case

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

That is:

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

R = PolynomialRing(Zmod(2),"x")
## Here are the elements of degree at most 4 for p in R.polynomials(4): print(p)
x^4 x^4 + 1 x^4 + x x^4 + x + 1 x^4 + x^2 x^4 + x^2 + 1 x^4 + x^2 + x x^4 + x^2 + x + 1 x^4 + x^3 x^4 + x^3 + 1 x^4 + x^3 + x x^4 + x^3 + x + 1 x^4 + x^3 + x^2 x^4 + x^3 + x^2 + 1 x^4 + x^3 + x^2 + x x^4 + x^3 + x^2 + x + 1
for p in R.polynomials(4): print("{} factors as {}".format(p,p.factor())) if p.is_irreducible(): print("\t\t{} is irreducible!".format(p))
x^4 factors as x^4 x^4 + 1 factors as (x + 1)^4 x^4 + x factors as x * (x + 1) * (x^2 + x + 1) x^4 + x + 1 factors as x^4 + x + 1 x^4 + x + 1 is irreducible! x^4 + x^2 factors as x^2 * (x + 1)^2 x^4 + x^2 + 1 factors as (x^2 + x + 1)^2 x^4 + x^2 + x factors as x * (x^3 + x + 1) x^4 + x^2 + x + 1 factors as (x + 1) * (x^3 + x^2 + 1) x^4 + x^3 factors as (x + 1) * x^3 x^4 + x^3 + 1 factors as x^4 + x^3 + 1 x^4 + x^3 + 1 is irreducible! x^4 + x^3 + x factors as x * (x^3 + x^2 + 1) x^4 + x^3 + x + 1 factors as (x + 1)^2 * (x^2 + x + 1) x^4 + x^3 + x^2 factors as x^2 * (x^2 + x + 1) x^4 + x^3 + x^2 + 1 factors as (x + 1) * (x^3 + x + 1) x^4 + x^3 + x^2 + x factors as x * (x + 1)^3 x^4 + x^3 + x^2 + x + 1 factors as x^4 + x^3 + x^2 + x + 1 x^4 + x^3 + x^2 + x + 1 is irreducible!

Irreducible polynomials

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

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

In fact there are irreducible polynomials of every degree over Z2\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 mm and nn are equivalent modulo pZp\in \mathbb{Z} if when you apply the division theorem,

m=qmp+rm m = q_mp + r_m

n=qnp+rn n = q_np + r_n

and rm=rnr_m = r_n (with 0rn<qn0\leq r_n < q_n and 0rm<qm0 \leq r_m < q_m).

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

This means that inverses exist for every nonzero element.

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

Polynomial version

Two polynomials with coefficients in Z2\mathbb{Z}_2 mm and nn are equivalent modulo pp (where pp also has coefficients in Z2\mathbb{Z}_2) if when you apply the division theorem,

m=qmp+rm m = q_mp + r_m

n=qnp+rn n = q_np + r_n

and rm=rnr_m = r_n (with 0deg(rn)<deg(qn)0\leq \deg(r_n) < \deg(q_n) and 0deg(rm)<deg(qm)0 \leq \deg(r_m) < \deg(q_m)).

If pp 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 dd of pp.

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

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

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

There are exactly 2d2^d equivalence classes.

Let's do a Sage example!

p
x^4 + x^3 + x^2 + x + 1
F = GF(2**4,"x",modulus=p)
for p in F: print(p)
0 x + 1 x^2 + 1 x^3 + x^2 + x + 1 x^3 + x^2 + x x^3 + x^2 + 1 x^3 x^2 + x + 1 x^3 + 1 x^2 x^3 + x^2 x^3 + x + 1 x x^2 + x x^3 + x 1

Some observations

Let's make some observations about this field:

  1. There are indeed exactly 24=162^4 = 16 elements.
  2. The elements are precisely the polynomials of degree less than d=4d=4 with coefficients in Z2\mathbb{Z}_2.
  3. These are exactly the possible remainders when you divide a polynomial with coefficients in Z2\mathbb{Z}_2 by p(x)=x4+x3+x2+x+1p(x) = x^4 + x^3 + x^2 + x + 1.

Why are there no elements of degree higher than 3?

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

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

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

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

ex = F("x") for i in range(20): print("x^{:02} = {}".format(i,ex**i))
x^00 = 1 x^01 = x x^02 = x^2 x^03 = x^3 x^04 = x^3 + x^2 + x + 1 x^05 = 1 x^06 = x x^07 = x^2 x^08 = x^3 x^09 = x^3 + x^2 + x + 1 x^10 = 1 x^11 = x x^12 = x^2 x^13 = x^3 x^14 = x^3 + x^2 + x + 1 x^15 = 1 x^16 = x x^17 = x^2 x^18 = x^3 x^19 = x^3 + x^2 + x + 1

Exercise

Do the reduction x4x3+x2+x+1modx4+x3+x2+x+1x^4 \equiv x^3 + x^2 + x+ 1 \mod x^4 + x^3 + x^2 + x + 1 by hand.

Solution:

Since p(x)=x4+x3+x2+x+10p(x) = x^4 + x^3 + x^2 + x + 1 \equiv 0, it follows that x3+x2+x+1x4x^3 + x^2 + x + 1 \equiv x^4.

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

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

F = GF(2**4,"x",modulus=x^4+x+1)
for p in F: print(p)
0 x x^2 x^3 x + 1 x^2 + x x^3 + x^2 x^3 + x + 1 x^2 + 1 x^3 + x x^2 + x + 1 x^3 + x^2 + x x^3 + x^2 + x + 1 x^3 + x^2 + 1 x^3 + 1 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 xx generate all of the nonzero elements.

ex = F("x") for i in range(16): print("x^{:02} = {}".format(i,ex**i))
x^00 = 1 x^01 = x x^02 = x^2 x^03 = x^3 x^04 = x + 1 x^05 = x^2 + x x^06 = x^3 + x^2 x^07 = x^3 + x + 1 x^08 = x^2 + 1 x^09 = x^3 + x x^10 = x^2 + x + 1 x^11 = x^3 + x^2 + x x^12 = x^3 + x^2 + x + 1 x^13 = x^3 + x^2 + 1 x^14 = x^3 + 1 x^15 = 1

Addition in GF(16)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 Z2\mathbb{Z}_2.

For example:

(x3+x2+1)+(x3+x2)x3+1(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 x3+1x^3 + 1 but rather the remainder when it is divided by x4+x+1x^4+x+1.

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

Multiplication in GF(16)GF(16)

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

That's because multiplication does increase the degree.

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

(x3+x2+1)(x3+x2)=x6+x5+x5+x4+x3+x2x6+x4+x3+x2(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 x6+x4+x3+x2x^6 + x^4 + x^3 +x^2 but rather its remainder when we divide it by x4+x+1x^4+x+1.

We can use Sage to compute the remainder:

R("x^6+x^4+x^3+x^2")%R("x^4+x+1")
x + 1

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

F("x^3+x^2+1")*F("x^3+x^2")
x + 1

Funny Arithmetic over Nybbles

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

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

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

The rule is:

cd1xd1+cd2xd2++c1x+c0cd1cd2c1c0c_{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

x3+x2+11101x^3 + x^2 + 1 \mapsto 1101

and

x3+x21100x^3 + x^2 \mapsto 1100

and

000000 \mapsto 0000

etc.

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

Here it is in Sage.

for q in F: print("{:17} -> {:0x}".format(str(q),q.integer_representation()))
0 -> 0 x -> 2 x^2 -> 4 x^3 -> 8 x + 1 -> 3 x^2 + x -> 6 x^3 + x^2 -> c x^3 + x + 1 -> b x^2 + 1 -> 5 x^3 + x -> a x^2 + x + 1 -> 7 x^3 + x^2 + x -> e x^3 + x^2 + x + 1 -> f x^3 + x^2 + 1 -> d x^3 + 1 -> 9 1 -> 1

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

(x3+x2+1)+(x3+x2)x3+1(x^3+x^2+1) + (x^3+x^2) \equiv x^3 + 1.

would look like

d+c=9d + c = 9.

And the fact that

(x3+x2+1)(x3+x2)=x6+x5+x5+x4+x3+x2x6+x4+x3+x2x+1(modx4+x+1)(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

dc=3d\cdot c = 3.

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

F.multiplication_table(names = [hex(i) for i in range(16)])
* 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xa 0xb 0xc 0xd 0xe 0xf +---------------------------------------------------------------- 0x0| 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x1| 0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xa 0xb 0xc 0xd 0xe 0xf 0x2| 0x0 0x2 0x4 0x6 0x8 0xa 0xc 0xe 0x3 0x1 0x7 0x5 0xb 0x9 0xf 0xd 0x3| 0x0 0x3 0x6 0x5 0xc 0xf 0xa 0x9 0xb 0x8 0xd 0xe 0x7 0x4 0x1 0x2 0x4| 0x0 0x4 0x8 0xc 0x3 0x7 0xb 0xf 0x6 0x2 0xe 0xa 0x5 0x1 0xd 0x9 0x5| 0x0 0x5 0xa 0xf 0x7 0x2 0xd 0x8 0xe 0xb 0x4 0x1 0x9 0xc 0x3 0x6 0x6| 0x0 0x6 0xc 0xa 0xb 0xd 0x7 0x1 0x5 0x3 0x9 0xf 0xe 0x8 0x2 0x4 0x7| 0x0 0x7 0xe 0x9 0xf 0x8 0x1 0x6 0xd 0xa 0x3 0x4 0x2 0x5 0xc 0xb 0x8| 0x0 0x8 0x3 0xb 0x6 0xe 0x5 0xd 0xc 0x4 0xf 0x7 0xa 0x2 0x9 0x1 0x9| 0x0 0x9 0x1 0x8 0x2 0xb 0x3 0xa 0x4 0xd 0x5 0xc 0x6 0xf 0x7 0xe 0xa| 0x0 0xa 0x7 0xd 0xe 0x4 0x9 0x3 0xf 0x5 0x8 0x2 0x1 0xb 0x6 0xc 0xb| 0x0 0xb 0x5 0xe 0xa 0x1 0xf 0x4 0x7 0xc 0x2 0x9 0xd 0x6 0x8 0x3 0xc| 0x0 0xc 0xb 0x7 0x5 0x9 0xe 0x2 0xa 0x6 0x1 0xd 0xf 0x3 0x4 0x8 0xd| 0x0 0xd 0x9 0x4 0x1 0xc 0x8 0x5 0x2 0xf 0xb 0x6 0x3 0xe 0xa 0x7 0xe| 0x0 0xe 0xf 0x1 0xd 0x3 0x2 0xc 0x9 0x7 0x6 0x8 0x4 0xa 0xb 0x5 0xf| 0x0 0xf 0xd 0x2 0x9 0x6 0x4 0xb 0x1 0xe 0xc 0x3 0x8 0x7 0x5 0xa

Funny arithmetic on bytes

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

We just need a bigger field.

GF256 = GF(2^8,"x",modulus=x^8+x^4+x^3+x+1)

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×0xaf=0x8b.0x66 \times 0xaf = 0x8b.

p = GF256.fetch_int(0x66) q = GF256.fetch_int(0xAF) result = p*q result
x^7 + x^3 + x + 1
print("{:0x}".format(result.integer_representation()))
8b

Wait...why are we using a field?

So far we have not made any use of inverses.

We have been using GF(2d)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(2d)GF(2^d) is to use the inverse operation as a kind of substitution.

If we call this substitution operation, SS then

S(p)=p1modx8+x4+x3+x1.S(p) = p^{-1} \mod x^8 + x^4 +x^3+x_1.

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(pq)S(p)S(q).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.

firstrow="{:8}".format("") for i in range(16): firstrow += "{:6}".format(hex(i)) print(firstrow) print("-"*len(firstrow)) for i in range(16): rowstring = "{:4}:".format(hex(i)) for j in range(16): hexbyte = 16*i+j if hexbyte==0: rowstring += "{:6}".format(0) continue p = GF256.fetch_int(hexbyte) pinv = 1/p rowstring += "{:6x}".format(pinv.integer_representation()) print(rowstring)
0x0 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xa 0xb 0xc 0xd 0xe 0xf -------------------------------------------------------------------------------------------------------- 0x0 : 0 1 8d f6 cb 52 7b d1 e8 4f 29 c0 b0 e1 e5 c7 0x1 : 74 b4 aa 4b 99 2b 60 5f 58 3f fd cc ff 40 ee b2 0x2 : 3a 6e 5a f1 55 4d a8 c9 c1 a 98 15 30 44 a2 c2 0x3 : 2c 45 92 6c f3 39 66 42 f2 35 20 6f 77 bb 59 19 0x4 : 1d fe 37 67 2d 31 f5 69 a7 64 ab 13 54 25 e9 9 0x5 : ed 5c 5 ca 4c 24 87 bf 18 3e 22 f0 51 ec 61 17 0x6 : 16 5e af d3 49 a6 36 43 f4 47 91 df 33 93 21 3b 0x7 : 79 b7 97 85 10 b5 ba 3c b6 70 d0 6 a1 fa 81 82 0x8 : 83 7e 7f 80 96 73 be 56 9b 9e 95 d9 f7 2 b9 a4 0x9 : de 6a 32 6d d8 8a 84 72 2a 14 9f 88 f9 dc 89 9a 0xa : fb 7c 2e c3 8f b8 65 48 26 c8 12 4a ce e7 d2 62 0xb : c e0 1f ef 11 75 78 71 a5 8e 76 3d bd bc 86 57 0xc : b 28 2f a3 da d4 e4 f a9 27 53 4 1b fc ac e6 0xd : 7a 7 ae 63 c5 db e2 ea 94 8b c4 d5 9d f8 90 6b 0xe : b1 d d6 eb c6 e cf ad 8 4e d7 e3 5d 50 1e b3 0xf : 5b 23 38 34 68 46 3 8c dd 9c 7d a0 cd 1a 41 1c

Other finite fields

So far we have explored only finite fields of the form GF(2d)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 pp and every counting number dd there is a unique (up to isomorphism) field of cardinality pdp^d (denoted GF(pd)GF(p^d)). There are no other finite fields.


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

More generally, for any prime pp,

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


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