 CoCalc Public FilesCrypto_Fall_20 / polyring / poly.sagews
Author: Hunter Johnson
Views : 52
Compute Environment: Ubuntu 20.04 (Default)

### 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$:

$p + 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:

$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,$ and $s$ are polynomials, then

$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 $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

$n = qm + r$

Polynomial division theorem

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

$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 $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

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

and

$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)$

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$?

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 $\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,

$m = q_mp + r_m$

$n = q_np + r_n$

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,

$m = q_mp + r_m$

$n = q_np + r_n$

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!

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

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.

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 $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$.

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 $x$ 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)$

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:

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(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.

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

$(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:

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 \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(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

$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(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(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).