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.
Polynomial GF(2) Factoring and Irreducible Polynomials |
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 |
The code is:
from galois_field import GFpn import sys a=([1,0],[1,1],[1,1,1],[1,0,1,1],[1,1,0,1],[1,0,0,1,1],[1,1,0,0,1],[1,1,1,1,1],[1,0,0,1,0,1],[1,0,1,0,0,1],[1,0,1,1,1,1],[1,1,0,1,1,1],[1,1,1,0,1,1],[1,1,1,1,0,1],[1,0,0,0,0,1,1],[1,0,0,1,0,0,1],[1,0,1,0,1,1,1],[1,0,1,1,0,1,1],[1,1,0,0,0,0,1],[1,1,0,0,1,1,1],[1,1,0,1,1,0,1],[1,1,1,0,0,1,1],[1,1,1,0,1,0,1]) tofind=[1,0,0,1] p=[1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1] if (len(sys.argv)>1): tofind=eval("["+sys.argv[1].replace(" ","")+"]") if (len(tofind)>10): sys.exit() try: gf = GFpn(2,p ) except Exception as e: print ("Error:" ,e) sys.exit() tofindval = gf.elm(tofind) print (f"Factors of {tofindval}") # Try one factor try: for i in range(0,len(a)): aval1 = gf.elm(a[i]) res1=aval1 if (str(tofindval)==str(res1)): print(a[i]) print(f"({aval1})") sys.exit() except: sys.exit() # Try two factors try: for i in range(0,len(a)): for j in range(i,len(a)): aval1 = gf.elm(a[i]) aval2 = gf.elm(a[j]) res2=aval1*aval2 if (str(tofindval)==str(res2)): print(a[i],a[j]) print(f"({aval1})x({aval2})") sys.exit() except: sys.exit() # Try three factors try: for i in range(0,len(a)): for j in range(i,len(a)): for k in range(j,len(a)): aval1 = gf.elm(a[i]) aval2 = gf.elm(a[j]) aval3 = gf.elm(a[k]) res3=aval1*aval2*aval3 if (str(tofindval)==str(res3)): print(f"({aval1})x({aval2})x({aval3})") print(a[i],a[j],a[k]) sys.exit() except: sys.exit()
A sample run gives:
Factors of 1x^4 + 1x^3 + 1x^2 + 1 [1, 1] [1, 0, 1, 1] (1x + 1)*(1x^3 + 1x + 1)
In this case \(x^4 + x^3 + x^2 + 1\) can be factorized by (\(x + 1)\) and (\(x^3 + 1x + 1\)) in GF(2). This is true because:
\(f=(x+1)(x^3+x+1)\)
\(f=x^4 + x^2 + x + x^3 + x + 1\)
\(f=x^4 + x^3 + x^2 + 1\)