Primitive and Conway Polynomials

Primitive and Conway Polynomials

In public key methods, we use the (mod p) operation to reduce the field. With a prime number of p, we end up with values from 0 to p-1. The methods we then have are:

M^e (mod N) [RSA]

y²=x³+a.x+b (mod p) [ECC]

Y=g^x (mod p) [Discrete logs]

And so in the Diffie-Hellman method we use:

A = g^a (mod p)
B = g^b (mod p)
K1 = A^b (mod p)
K2 = B^a (mod p)

But, quantum computers will be able to crack methods that use the (mod p) operation. Our focus is now on lattice methods, and which convert the bit patterns in polynomial, such as:

54->0b110110 -> x⁵+x⁴+x²+x
41->0b101001 -> x⁵+x³+1

This is known as GF(2⁶) and where we have six bits for each value. We then use polynomial addition, subtraction, division, and multiplication. If we multiply 54 times 41 we get:

(x⁵+x⁴+x²+x).(x⁵+x³+1) = x¹⁰+x⁸+x⁵+x⁹+x⁷+x⁴+x⁷+x⁵+x²+ x⁶+x⁴+x

= x¹⁰+x⁹+x⁸+(x⁷+x⁷)+x⁶+(x⁵+x⁵)+(x⁴+x⁴)+x²+x = x¹⁰+x⁹+x⁸+x⁶+x²+x

Let’s say that we want the maximum degree to be 6 (x⁵), then we divide by an irreducible polynomial. For a degree of 6, we get an irreducible polynomial of x⁶ + x⁴ + x³ + x + 1:

                          x^4+x^3+x^2
                        -------------------------------------
x^6 + x^4 + x^3 + x + 1 | x^10+x^9+x^8+        x^6+           +x^2+x
                          x^10+   +x^8+    x^7+    x^5+x^4
                          ------------------------------------------
                               x^9+        x^7+x^6+x^5+x^4    +x^2+x
                               x^9+        x^7+x^6     x^4+x^3
                               ------------------------------------
                                                   x^5    +x^3+x^2+x
                                  

The result is then (x⁵+x⁴+x²+x).(x⁵+x³+1) = x⁵+x³+x²+x … and which is 46 as an integer (b101110). We can check this against a GF(2⁶) table for multiplication [here]:

Primitive and Conway polynomials

With x²+1, we can expand to (x+1)(x+1), as this equals (x²+x+x+1), and which reduces to (x²+1). An irreducible polynomial cannot be expanded into factors. This includes:

• x irreducible [Try!].
• x+1 irreducible [Try!].
• x²+x+1 irreducible [Try!] .
• x³+x+1 irreducible [Try!].
• x⁴+x+1 irreducible [Try!].

An irreducible polynomial is useful, and where we can divide by it, and reduce the maximum power in our polynomial values. A primitive polynomial is an irreducible polynomial and is the minimal derivation of the polynomial. With a degree of six, we have three irreducible polynomials:

x^6 + x^1 + 1
x^6 + x^5 + x^2 + x^1 + 1
x^6 + x^5 + x^3 + x^2 + 1

The primitive polynomial is x⁶ + x¹ + 1. Another type of irreducible polynomial is a Conway polynomial. In the following, we can produce a primitive polynomial and Conway polynomial for various degrees [here]:

import sys
import galois

p=2
n=2

if (len(sys.argv)>1):
  p=int(sys.argv[1])
if (len(sys.argv)>2):
  n=int(sys.argv[2])


print (f"== GF({p}^{n}) ==")


r=galois.primitive_poly(p, n)
print(f"\nPrimitive Polynomial for GF({p}^{n}):\t{r}")
print(f"  Integer: \t{int(r)}\tBinary:\t{bin(r)} ")

r=galois.conway_poly(p, n)
print(f"Conway Polynomial for GF({p}^{n}):\t\t{r}")
print(f"  Integer: \t{int(r)}\tBinary:\t{bin(r)} ")

We can then run for GF(2²):

== GF(2^2) ==

Primitive Polynomial for GF(2^2): x^2 + x + 1
  Integer:  7 Binary: 0b111 
Conway Polynomial for GF(2^2):  x^2 + x + 1
  Integer:  7 Binary: 0b111 

and GF(2³):

== GF(2^3) ==

Primitive Polynomial for GF(2^3): x^3 + x + 1
  Integer:  11 Binary: 0b1011 
Conway Polynomial for GF(2^3):  x^3 + x + 1
  Integer:  11 Binary: 0b1011 

and GF(2⁶):

== GF(2^6) ==

Primitive Polynomial for GF(2^6): x^6 + x + 1
  Integer:  67 Binary: 0b1000011 
Conway Polynomial for GF(2^6):  x^6 + x^4 + x^3 + x + 1
  Integer:  91 Binary: 0b1011011

Conclusions

Public key encryption methods are on the way out, and polynomial operations are on the way in.

https://billatnapier.medium.com/membership