A Conway and primitive polynomial for GF(\(p^n\)) are ones what cannot be factorized.
Conway and primitive polynomial GF(p^n) |
Outline
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:/p>
(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. 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 miminal derviation 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:
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^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^3\)):
== 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^4\)):
== GF(2^4) == Primitive Polynomial for GF(2^4): x^4 + x + 1 Integer: 19 Binary: 0b10011 Conway Polynomial for GF(2^4): x^4 + x + 1 Integer: 19 Binary: 0b10011
and GF(\(2^5\)):
== GF(2^5) == Primitive Polynomial for GF(2^5): x^5 + x^2 + 1 Integer: 37 Binary: 0b100101 Conway Polynomial for GF(2^5): x^5 + x^2 + 1 Integer: 37 Binary: 0b100101
and GF(\(2^6\)):
== 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