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 |
Theory
The following defines the factorization of polynomials for GF(2) [here].
Index | Binary | Polynomial | Factors |
2 | 10 | x | irreducible |
3 | 11 | x+1 | irreducible |
4 | 100 | x2 | (x)(x) |
5 | 101 | x2+1 | (x+1)(x+1) |
6 | 110 | x2+x | (x)(x+1) |
7 | 111 | x2+x+1 | irreducible |
8 | 1000 | x3 | (x)(x)(x) |
9 | 1001 | x3+1 | (x+1)(x2+x+1) |
10 | 1010 | x3+x | (x)(x+1)(x+1) |
11 | 1011 | x3+x+1 | irreducible |
12 | 1100 | x3+x2 | (x)(x)(x+1) |
13 | 1101 | x3+x2+1 | irreducible |
14 | 1110 | x3+x2+x | (x)(x2+x+1) |
15 | 1111 | x3+x2+x+1 | (x+1)(x+1)(x+1) |
16 | 10000 | x4 | (x)(x)(x)(x) |
17 | 10001 | x4+1 | (x+1)(x+1)(x+1)(x+1) |
18 | 10010 | x4+x | (x)(x+1)(x2+x+1) |
19 | 10011 | x4+x+1 | irreducible |
20 | 10100 | x4+x2 | (x)(x)(x+1)(x+1) |
21 | 10101 | x4+x2+1 | (x2+x+1)(x2+x+1) |
22 | 10110 | x4+x2+x | (x)(x3+x+1) |
23 | 10111 | x4+x2+x+1 | (x+1)(x3+x2+1) |
24 | 11000 | x4+x3 | (x)(x)(x)(x+1) |
25 | 11001 | x4+x3+1 | irreducible |
26 | 11010 | x4+x3+x | (x)(x3+x2+1) |
27 | 11011 | x4+x3+x+1 | (x+1)(x+1)(x2+x+1) |
28 | 11100 | x4+x3+x2 | (x)(x)(x2+x+1) |
29 | 11101 | x4+x3+x2+1 | (x+1)(x3+x+1) |
30 | 11110 | x4+x3+x2+x | (x)(x+1)(x+1)(x+1) |
31 | 11111 | x4+x3+x2+x+1 | irreducible |
32 | 100000 | x5 | (x)(x)(x)(x)(x) |
33 | 100001 | x5+1 | (x+1)(x4+x3+x2+x+1) |
34 | 100010 | x5+x | (x)(x+1)(x+1)(x+1)(x+1) |
35 | 100011 | x5+x+1 | (x2+x+1)(x3+x2+1) |
36 | 100100 | x5+x2 | (x)(x)(x+1)(x2+x+1) |
37 | 100101 | x5+x2+1 | irreducible |
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) |
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\)