This page implements Galois Fields GF(\(p^n\)) with Python and provides a table of multiplication. With this \(p\) is a prime number and \(n\) ranges from 1 to \(n-1\). A GF(\(2^4\)) will have a range of outputs from 0 to 15. In this case, we will determine the parameters for GF(\(2^n\)), GF(\(3^n\)), GF(\(5^n\)), and GF(\(5^n\)). This includes finding the irreducible polynomial for the Galois Field for a given value of \(p\).
Irreducible polynomial for GF(\(p^n\)) for a given \(p\) and for \(n\) values |
Outline
In data communications and cryptography, we can represent binary values as as polynomials in GF(2). These can then be processed with GF(2) arithmetic. A value of \(10011\) can then be represented in a polynomial form as \(x^4+x+1\). Every non-prime value can be reduced to a multiplication of prime numbers. For example, 14 is \(2 \times 7\) and 16 is \(2 \times 2 \times 2 \times 2\). The same can be done for polynomials in GF(2), and where we can factorize a polynomial. Within polynomials, the prime number equivalents are known as irreducible, as they cannot be factored. This page allows for a polynomial value to be entered, and the determines if it is irreducible, or has two or three factors. The table defined below outlines the factors involved.
The program we will use is:
import galois import sys p=2 if (len(sys.argv)>1): p=int(sys.argv[1]) print(f"Irreducible Poly\n") for n in range(1,12): GF = galois.GF(p**n) print(f"Degree {n}: {GF.irreducible_poly}")
For GF(\(2^n\)) we get:
GF(2^1): x + 1 GF(2^2): x^2 + x + 1 GF(2^3): x^3 + x + 1 GF(2^4): x^4 + x + 1 GF(2^5): x^5 + x^2 + 1 GF(2^6): x^6 + x^4 + x^3 + x + 1 GF(2^7): x^7 + x + 1 GF(2^8): x^8 + x^4 + x^3 + x^2 + 1
This means that we can use \(x^2 + x + 1 \) as our irreducible polynomial. We can also see that that the order shows that there are four possible values (0,1,2,3), and that the degree is two. For GF(\(2^8\)) we get:
For GF(\(3^n\)), we get:
GF(3^1): x + 1 GF(3^2): x^2 + 2x + 2 GF(3^3): x^3 + 2x + 1 GF(3^4): x^4 + 2x^3 + 2 GF(3^5): x^5 + 2x + 1 GF(3^6): x^6 + 2x^4 + x^2 + 2x + 2 GF(3^7): x^7 + 2x^2 + 1 GF(3^8): x^8 + 2x^5 + x^4 + 2x^2 + 2x + 2
For GF(\(5^n\)), we get:
GF(5^1): x + 3 GF(5^2): x^2 + 4x + 2 GF(5^3): x^3 + 3x + 3 GF(5^4): x^4 + 4x^2 + 4x + 2 GF(5^5): x^5 + 4x + 3 GF(5^6): x^6 + x^4 + 4x^3 + x^2 + 2 GF(5^7): x^7 + 3x + 3 GF(5^8): x^8 + x^4 + 3x^2 + 4x + 2
For GF(\(7^n\)), we get:
GF(7^1): x + 4 GF(7^2): x^2 + 6x + 3 GF(7^3): x^3 + 6x^2 + 4 GF(7^4): x^4 + 5x^2 + 4x + 3 GF(7^5): x^5 + x + 4 GF(7^6): x^6 + x^4 + 5x^3 + 4x^2 + 6x + 3 GF(7^7): x^7 + 6x + 4 GF(7^8): x^8 + 4x^3 + 6x^2 + 2x + 3
For GF(\(11^n\)), we get:
GF(11^1): x + 9 GF(11^2): x^2 + 7x + 2 GF(11^3): x^3 + 2x + 9 GF(11^4): x^4 + 8x^2 + 10x + 2 GF(11^5): x^5 + 10x^2 + 9 GF(11^6): x^6 + 3x^4 + 4x^3 + 6x^2 + 7x + 2 GF(11^7): x^7 + 4x + 9 GF(11^8): x^8 + 7x^4 + 7x^3 + x^2 + 7x + 2
For GF(\(13^n\)), we get:
GF(13^1): x + 11 GF(13^2): x^2 + 12x + 2 GF(13^3): x^3 + 2x + 11 GF(13^4): x^4 + 3x^2 + 12x + 2 GF(13^5): x^5 + 4x + 11 GF(13^6): x^6 + 10x^3 + 11x^2 + 11x + 2 GF(13^7): x^7 + 3x + 11 GF(13^8): x^8 + 8x^4 + 12x^3 + 2x^2 + 3x + 2
For GF(\(17^n\)), we get:
GF(17^1): x + 14 GF(17^2): x^2 + 16x + 3 GF(17^3): x^3 + x + 14 GF(17^4): x^4 + 7x^2 + 10x + 3 GF(17^5): x^5 + x + 14 GF(17^6): x^6 + 2x^4 + 10x^2 + 3x + 3 GF(17^7): x^7 + 12x + 14 GF(17^8): x^8 + 11x^4 + 12x^3 + 6x + 3
For GF(\(19^n\)), we get:
GF(19^1): x + 17 GF(19^2): x^2 + 18x + 2 GF(19^3): x^3 + 4x + 17 GF(19^4): x^4 + 2x^2 + 11x + 2 GF(19^5): x^5 + 5x + 17 GF(19^6): x^6 + 17x^3 + 17x^2 + 6x + 2 GF(19^7): x^7 + 6x + 17 GF(19^8): x^8 + x^4 + 12x^3 + 10x^2 + 3x + 2
For GF(\(23^n\)), we get:
GF(23^1): x + 18 GF(23^2): x^2 + 21x + 5 GF(23^3): x^3 + 2x + 18 GF(23^4): x^4 + 3x^2 + 19x + 5 GF(23^5): x^5 + 3x + 18 GF(23^6): x^6 + x^4 + 9x^3 + 9x^2 + x + 5 GF(23^7): x^7 + 21x + 18 GF(23^8): x^8 + 3x^4 + 20x^3 + 5x^2 + 3x + 5
For GF(\(27^n\)), we get:
GF(27^1): x^3 + 2x + 1 GF(27^2): x^6 + 2x^4 + x^2 + 2x + 2 GF(27^3): x^9 + 2x^3 + 2x^2 + x + 1 GF(27^4): x^12 + x^6 + x^5 + x^4 + x^2 + 2 GF(27^5): x^15 + 2x^8 + x^5 + 2x^2 + x + 1 GF(27^6): x^18 + x^10 + 2x^8 + 2x^6 + x^5 + 2x^4 + 2x^2 + 2 GF(27^7): x^21 + 2x^10 + 2x^8 + 2x^6 + x^5 + 2x^3 + 2x + 1 GF(27^8): x^24 + x^14 + 2x^11 + 2x^8 + 2x^6 + 2x^4 + 2x^3 + 2x + 2
For GF(\(31^n\)), we get:
GF(31^1): x + 28 GF(31^2): x^2 + 29x + 3 GF(31^3): x^3 + x + 28 GF(31^4): x^4 + 3x^2 + 16x + 3 GF(31^5): x^5 + 7x + 28 GF(31^6): x^6 + 19x^3 + 16x^2 + 8x + 3 GF(31^7): x^7 + x + 28 GF(31^8): x^8 + 25x^3 + 12x^2 + 24x + 3
Theory
The following defines the factorization of polynomials for GF(2) [here].
Index | Binary | Polynomial | Factors |
2 | 10 | x | irreducible [Try!] |
3 | 11 | x+1 | irreducible [Try!] |
4 | 100 | x2 | (x)(x) [Try!] |
5 | 101 | x2+1 | (x+1)(x+1) [Try!] |
6 | 110 | x2+x | (x)(x+1) [Try!] |
7 | 111 | x2+x+1 | irreducible [Try!] |
8 | 1000 | x3 | (x)(x)(x) [Try!] |
9 | 1001 | x3+1 | (x+1)(x2+x+1) [Try!] |
10 | 1010 | x3+x | (x)(x+1)(x+1) [Try!] |
11 | 1011 | x3+x+1 | irreducible [Try!] |
12 | 1100 | x3+x2 | (x)(x)(x+1) [Try!] |
13 | 1101 | x3+x2+1 | irreducible [Try!] |
14 | 1110 | x3+x2+x | (x)(x2+x+1) [Try!] |
15 | 1111 | x3+x2+x+1 | (x+1)(x+1)(x+1) [Try!] |
16 | 10000 | x4 | (x)(x)(x)(x) [Try!] |
17 | 10001 | x4+1 | (x+1)(x+1)(x+1)(x+1) [Try!] |
18 | 10010 | x4+x | (x)(x+1)(x2+x+1) [Try!] |
19 | 10011 | x4+x+1 | irreducible [Try!] |
20 | 10100 | x4+x2 | (x)(x)(x+1)(x+1) [Try!] |
21 | 10101 | x4+x2+1 | (x2+x+1)(x2+x+1) [Try!] |
22 | 10110 | x4+x2+x | (x)(x3+x+1) [Try!] |
23 | 10111 | x4+x2+x+1 | (x+1)(x3+x2+1) [Try!] |
24 | 11000 | x4+x3 | (x)(x)(x)(x+1) [Try!] |
25 | 11001 | x4+x3+1 | irreducible [Try!] |
26 | 11010 | x4+x3+x | (x)(x3+x2+1) [Try!] |
27 | 11011 | x4+x3+x+1 | (x+1)(x+1)(x2+x+1) [Try!] |
28 | 11100 | x4+x3+x2 | (x)(x)(x2+x+1) [Try!] |
29 | 11101 | x4+x3+x2+1 | (x+1)(x3+x+1) [Try!] |
30 | 11110 | x4+x3+x2+x | (x)(x+1)(x+1)(x+1) [Try!] |
31 | 11111 | x4+x3+x2+x+1 | irreducible [Try!] |
32 | 100000 | x5 | (x)(x)(x)(x)(x) [Try!] |
33 | 100001 | x5+1 | (x+1)(x4+x3+x2+x+1) [Try!] |
34 | 100010 | x5+x | (x)(x+1)(x+1)(x+1)(x+1) [Try!] |
35 | 100011 | x5+x+1 | (x2+x+1)(x3+x2+1) [Try!] |
36 | 100100 | x5+x2 | (x)(x)(x+1)(x2+x+1) [Try!] |
37 | 100101 | x5+x2+1 | irreducible [Try!] |
38 | 100110 | x5+x2+x | (x)(x4+x+1) |
39 | 100111 | x5+x2+x+1 | (x+1)(x+1)(x3+x+1) |
40 | 101000 | x5+x3 | (x)(x)(x)(x+1)(x+1) |
41 | 101001 | x5+x3+1 | irreducible |
42 | 101010 | x5+x3+x | (x)(x2+x+1)(x2+x+1) |
43 | 101011 | x5+x3+x+1 | (x+1)(x4+x3+1) |
44 | 101100 | x5+x3+x2 | (x)(x)(x3+x+1) |
45 | 101101 | x5+x3+x2+1 | (x+1)(x+1)(x+1)(x2+x+1) |
46 | 101110 | x5+x3+x2+x | (x)(x+1)(x3+x2+1) |
47 | 101111 | x5+x3+x2+x+1 | irreducible |
48 | 110000 | x5+x4 | (x)(x)(x)(x)(x+1) |
49 | 110001 | x5+x4+1 | (x2+x+1)(x3+x+1) |
50 | 110010 | x5+x4+x | (x)(x4+x3+1) |
51 | 110011 | x5+x4+x+1 | (x+1)(x+1)(x+1)(x+1)(x+1) |
52 | 110100 | x5+x4+x2 | (x)(x)(x3+x2+1) |
53 | 110101 | x5+x4+x2+1 | (x+1)(x4+x+1) |
54 | 110110 | x5+x4+x2+x | (x)(x+1)(x+1)(x2+x+1) |
55 | 110111 | x5+x4+x2+x+1 | irreducible |
56 | 111000 | x5+x4+x3 | (x)(x)(x)(x2+x+1) |
57 | 111001 | x5+x4+x3+1 | (x+1)(x+1)(x3+x2+1) |
58 | 111010 | x5+x4+x3+x | (x)(x+1)(x3+x+1) |
59 | 111011 | x5+x4+x3+x+1 | irreducible |
60 | 111100 | x5+x4+x3+x2 | (x)(x)(x+1)(x+1)(x+1) |
61 | 111101 | x5+x4+x3+x2+1 | irreducible |
62 | 111110 | x5+x4+x3+x2+x | (x)(x4+x3+x2+x+1) |
63 | 111111 | x5+x4+x3+x2+x+1 | (x+1)(x2+x+1)(x2+x+1) |
64 | 1000000 | x6 | (x)(x)(x)(x)(x)(x) |
65 | 1000001 | x6+1 | (x+1)(x+1)(x2+x+1)(x2+x+1) |
66 | 1000010 | x6+x | (x)(x+1)(x4+x3+x2+x+1) |
67 | 1000011 | x6+x+1 | irreducible |
68 | 1000100 | x6+x2 | (x)(x)(x+1)(x+1)(x+1)(x+1) |
69 | 1000101 | x6+x2+1 | (x3+x+1)(x3+x+1) |
70 | 1000110 | x6+x2+x | (x)(x2+x+1)(x3+x2+1) |
71 | 1000111 | x6+x2+x+1 | (x+1)(x5+x4+x3+x2+1) |
72 | 1001000 | x6+x3 | (x)(x)(x)(x+1)(x2+x+1) |
73 | 1001001 | x6+x3+1 | irreducible |
74 | 1001010 | x6+x3+x | (x)(x5+x2+1) |
75 | 1001011 | x6+x3+x+1 | (x+1)(x+1)(x+1)(x3+x2+1) |
76 | 1001100 | x6+x3+x2 | (x)(x)(x4+x+1) |
77 | 1001101 | x6+x3+x2+1 | (x+1)(x5+x4+x3+x+1) |
78 | 1001110 | x6+x3+x2+x | (x)(x+1)(x+1)(x3+x+1) |
79 | 1001111 | x6+x3+x2+x+1 | (x2+x+1)(x4+x3+1) |
80 | 1010000 | x6+x4 | (x)(x)(x)(x)(x+1)(x+1) |
81 | 1010001 | x6+x4+1 | (x3+x2+1)(x3+x2+1) |
82 | 1010010 | x6+x4+x | (x)(x5+x3+1) |
83 | 1010011 | x6+x4+x+1 | (x+1)(x2+x+1)(x3+x+1) |
84 | 1010100 | x6+x4+x2 | (x)(x)(x2+x+1)(x2+x+1) |
85 | 1010101 | x6+x4+x2+1 | (x+1)(x+1)(x+1)(x+1)(x+1)(x+1) |
86 | 1010110 | x6+x4+x2+x | (x)(x+1)(x4+x3+1) |
87 | 1010111 | x6+x4+x2+x+1 | irreducible |
88 | 1011000 | x6+x4+x3 | (x)(x)(x)(x3+x+1) |
89 | 1011001 | x6+x4+x3+1 | (x+1)(x5+x4+x2+x+1) |
90 | 1011010 | x6+x4+x3+x | (x)(x+1)(x+1)(x+1)(x2+x+1) |
91 | 1011011 | x6+x4+x3+x+1 | irreducible |
92 | 1011100 | x6+x4+x3+x2 | (x)(x)(x+1)(x3+x2+1) |
93 | 1011101 | x6+x4+x3+x2+1 | (x2+x+1)(x4+x3+x2+x+1) |
94 | 1011110 | x6+x4+x3+x2+x | (x)(x5+x3+x2+x+1) |
95 | 1011111 | x6+x4+x3+x2+x+1 | (x+1)(x+1)(x4+x+1) |
96 | 1100000 | x6+x5 | (x)(x)(x)(x)(x)(x+1) |
97 | 1100001 | x6+x5+1 | irreducible |
98 | 1100010 | x6+x5+x | (x)(x2+x+1)(x3+x+1) |
99 | 1100011 | x6+x5+x+1 | (x+1)(x+1)(x4+x3+x2+x+1) |
100 | 1100100 | x6+x5+x2 | (x)(x)(x4+x3+1) |
101 | 1100101 | x6+x5+x2+1 | (x+1)(x2+x+1)(x3+x2+1) |
102 | 1100110 | x6+x5+x2+x | (x)(x+1)(x+1)(x+1)(x+1)(x+1) |
103 | 1100111 | x6+x5+x2+x+1 | irreducible |
104 | 1101000 | x6+x5+x3 | (x)(x)(x)(x3+x2+1) |
105 | 1101001 | x6+x5+x3+1 | (x+1)(x+1)(x+1)(x3+x+1) |
106 | 1101010 | x6+x5+x3+x | (x)(x+1)(x4+x+1) |
107 | 1101011 | x6+x5+x3+x+1 | (x2+x+1)(x2+x+1)(x2+x+1) |
108 | 1101100 | x6+x5+x3+x2 | (x)(x)(x+1)(x+1)(x2+x+1) |
109 | 1101101 | x6+x5+x3+x2+1 | irreducible |
110 | 1101110 | x6+x5+x3+x2+x | (x)(x5+x4+x2+x+1) |
111 | 1101111 | x6+x5+x3+x2+x+1 | (x+1)(x5+x2+1) |
112 | 1110000 | x6+x5+x4 | (x)(x)(x)(x)(x2+x+1) |
113 | 1110001 | x6+x5+x4+1 | (x+1)(x5+x3+x2+x+1) |
114 | 1110010 | x6+x5+x4+x | (x)(x+1)(x+1)(x3+x2+1) |
115 | 1110011 | x6+x5+x4+x+1 | irreducible |
116 | 1110100 | x6+x5+x4+x2 | (x)(x)(x+1)(x3+x+1) |
117 | 1110101 | x6+x5+x4+x2+1 | irreducible |
118 | 1110110 | x6+x5+x4+x2+x | (x)(x5+x4+x3+x+1) |
119 | 1110111 | x6+x5+x4+x2+x+1 | (x+1)(x+1)(x+1)(x+1)(x2+x+1) |
120 | 1111000 | x6+x5+x4+x3 | (x)(x)(x)(x+1)(x+1)(x+1) |
121 | 1111001 | x6+x5+x4+x3+1 | (x2+x+1)(x4+x+1) |
122 | 1111010 | x6+x5+x4+x3+x | (x)(x5+x4+x3+x2+1) |
123 | 1111011 | x6+x5+x4+x3+x+1 | (x+1)(x5+x3+1) |
124 | 1111100 | x6+x5+x4+x3+x2 | (x)(x)(x4+x3+x2+x+1) |
125 | 1111101 | x6+x5+x4+x3+x2+1 | (x+1)(x+1)(x4+x3+1) |
126 | 1111110 | x6+x5+x4+x3+x2+x | (x)(x+1)(x2+x+1)(x2+x+1) |
127 | 1111111 | x6+x5+x4+x3+x2+x+1 | (x3+x+1)(x3+x2+1) |
283 | 100011011 | x8+x4+x3+x+1 | irreducible |