Tables of binary primitive Polynomials

Below tables of binary primitive polynomials are given which lead to polynomials w(x) of low weight and/or lowest degree. For the polynomial w(x) the equation w(x)2 = x mod p(x) holds. Clicking on the entries in the column Number of Polynomials leads - if there are more than one - to a window which contains all such primitive polynomials for degrees up to 32 together with the polynomials w(x).

Primitive polynomials having w(x) of weight two

A table for larger m, up to m=400 with primitive polynomials in hexadecimal notation, is given here.

m p(x) w(x) Number of Polynomials
2 x2+x+1 x+1 1
3 x3+x+1 x2+x 1
4 x4+x+1 x2+1 1
5 x5+x3+1 x3+x2 2
6 x6+x+1 x3+1 2
7 x7+x+1 x4+x 3
8 x8+x7+x5+x3+1 x7+x 2
9 x9+x5+1 x5+x3 5
10 x10+x8+x7+x4+x2+x+1 x7+x5 3
11 x11+x9+1 x6+x5 2
12 x12+x8+x7+x5+x4+x+1 x10+x7 2
13 x13+x10+x8+x7+x4+x3+x2+x+1 x9+1 5
14 x14+x11+x9+x8+x7+x4+x2+x+1 x9+x8 1
15 x15+x+1 x8+x 6
16 x16+x14+x13+x10+x9+x8+x7+x5+x4+x3+x2+x+1 x14+x13 2
17 x17+x3+1 x9+x2 8
18 x18+x16+x14+x11+x10+x9+x8+x7+x4+x3+1 x16+x6 1
19 x19+x18+x15+x11+x10+x9+x8+x6+x4+x3+1 x12+x11 5
20 x20+x15+x14+x13+x12+x9+x7+x6+x4+x3+x2+x+1 x18+x15 2
21 x21+x19+1 x11+x10 9
22 x22+x+1 x11+1 6
23 x23+x5+1 x12+x3 7
24 x24+x20+x19+x16+x15+x14+x13+x12+x10+x6+x3+x+1 x21+x4 1
25 x25+x3+1 x13+x2 7
26 x26+x24+x23+x22+x19+x17...x14+x11+x9+x8+x7+x4+x2+x+1 x19+x9 8
27 x27+x25+x24+x22+x21+x19+x18+x16+x15+x13+x12+...+x6+x5+x3+x2+1 x15+x 9
28 x28+x26+x25+x21+x17+x16+x12+x11+x9+x6+x5+x+1 x21+x9 3
29 x29+x27+1 x15+x14 8
30 x30+x27+x25+x17+x15+x11+x10+x9+x5+x4+x3+x+1 x21+x15 3
31 x31+x3+1 x16+x2 13
32 x32+x30...x27+x24+x23+x21+x18+x17+x14+x12+x10+x7+x6+x4...x2+1 x21+x 2

An entry like x30...x27 means that all powers between 30 and 27 occur.


Primitive polynomials having w(x) of weight three

m p(x) w(x) Number of Polynomials
2 - - 0
3 x3+x2+1 x2+x+1 1
4 x4+x3+1 x3+x2+x 1
5 x5+x4+x3+x2+1 x3+x+1 1
6 x6+x5+1 x4+x3+x 3
7 x7+x6+1 x4+x3+1 6
8 x8+x7+x2+x+1 x5+x4+x2 5
9 x9+x7+x6+x4+x3+x+1 x6+x5+1 3
10 x10+x9+x6+x5+x4+x3+x+x2+x+1 x6+x5++x4 6
11 x11+x9+x8+x7+x3+x+1 x8+x6+x5 13
12 x12+x11+x10+x6+x3+x2+1 x9+x7+x2 2
13 x13...x2+1 x7+x+1 22
14 x14...x5+x2+x+1 x8+x3+x2 16
15 x15+x14+1 x8+x7+1 22
16 x16+x15+x14+x13+x12+x11+1 x9+x6+x 22
17 x17+x16+x15+x14+1 x9+x7+1 28
18 x18...x5+x2+x+1 x10+x7+x4 24
19 x19...x14+1 x10+x7+1 39
20 x20+x19+x18+x17+x14...x+1 x11+x9+x8 25
21 x21...x16+x3+1 x11+x8+1 44
22 x22+x21+1 x12+x11+x 42
23 x23...x18+1 x12+x9+1 56
24 x24...x17+x10...1 x13+x9+x6 21
25 x25...x22+1 x13+x11+1 65
26 x26...x11+x2+x+1 x14+x6+x2 54
27 (x3+x)(x27+1)/(x3+1)+x x15+x14+x2 66
28 x28+x27+x6...1 x15+x14+x4 50
29 x29+x27+x26+x23...x21+x17+x15+x14+x10+x8+x7+x3+x+1 x17+x14+x12 117
30 x30+x29+x18...1 x16+x15+x10 54
31 x31...x28+1 x16+x14+1 129
32 x32...x19+x10...1 x17+x10+x6 53

The p(x) entry for m=27 reads 1011011011...01101 in binary notation.

Primitive polynomials having w(x) of degree ⌊(m+1)/2⌋ and weight as low as possible

For such polynomials taking the square root or squaring is very efficient as no modulo operations are necessary.
A table for larger m, up to m=400 with primitive polynomials in hexadecimal notation, is given here.

m p(x) w(x)
2 x2 + x + 1 x + 1
3 x3 + x + 1 x2 + x
4 x4 + x + 1 x2 + 1
5 x5 + x3 + 1 x3 + x2
6 x6 + x + 1 x3 + 1
7 x7 + x + 1 x4 + x
8 - -
9 x9 + x5 + 1 x 5 + x3
10 x10 + x8 + x6+x+1 x5 + x4 + x3 + 1
11 x11 + x9 + 1 x6 + x5
12 x12 + x6 + x4 + x + 1 x6 + x3 + x2 + 1
13 x13+x12...x2 + 1 x 7 + x + 1
14 x 14 + x6 + x4 + x + 1 x7 + x3 + x2 + 1
15 x15 + x + 1 x8 + x
16 x16 + x6 + x4 + x + 1 x8 + x3 + x2 + 1
17 x17 + x 3 + 1 x9 + x2
18 x18 + x8 + x2 + x + 1 x9 + x4 + x + 1
19 x19...x14 + 1 x10 + x7 + 1
20 x20 + x6 + x4 + x + 1 x10 + x3 + x2 + 1
21 x21 + x19 + 1 x11 + x10
22 x22 + x + 1 x11 + 1
23 x23 + x5 + 1 x12 + x3
24 x24 + x10 + x6 + x + 1 x12 + x5 + x3 + 1
25 x25 + x3 + 1 x13 + x2
26 x26 + x6 + x2 + x + 1 x13 + x3 + x + 1
27 x27 + x9 + x5 + x3 + 1 x14 + x5 + x3 + x2
28 x28 + x6 + x4 + x + 1 x14 + x3 + x2 + 1
29 x29 + x27 + 1 x15 + x14
30 x30 + x6 + x4 + x + 1 x15 + x3 + x2 + 1
31 x31 + x3 + 1 x16 + x2
32 x 32 + x14 + x6 + x + 1 x16 + x7 + x3 + 1