watson first 100 prims
PDF · 2 pages · 172.4 KB
Open PDF file
Reprint of a short paper from Mathematics of Computation by E. J. Watson of Manchester University, received December 1961, in Phil's Galois book folder. It describes how the list was computed on the Mercury computer by testing polynomials for small factors and for dividing x^N-1 with N=2^n-1. Polynomials are listed by the degrees of their terms. The table layout is scrambled in the text extraction, so individual entries are unreliable.
AI-written summary; may contain errors. This description is approximate.
Extracted text (machine-read; may contain errors)
Primitive Polynomials (Mod 2)
By E. J. Watson
The following list contains one example of a primitive polynomial (mod 2) for
each degree », 1 ^ n ^ 100. It was compiled with the aid of the Mercury computer
at Manchester University by the following method.
The polynomials P„(x) (mod 2) of degree n were tested in their natural order
until a primitive polynomial was found. The test comprised three stages. In the
first stage the small primes, of degree up to 9, were tried as possible factors (mod 2)
of Pn . If no factor was found P„ went forward to the second stage, which tested
whether Pn divides x" — 1, where N = 2" — 1. If it does, and N is prime (a Mer-
senne prime), this suffices to prove that P„ is primitive. If N is composite, however,
Pn might divide xM — 1, where M is a factor of N, and then Pn would not be primi-
tive. The third stage was, therefore, a trial of this possibility, in which M took the
values N/p, where p runs through the prime factors of N.
The two latter stages were carried out by a process in which the computer re-
peated the operations of squaring, possibly multiplying by x (depending on the
binary representation of M), then dividing by Pn . The prime factors of N were
taken from the tables of Kraïtchik [1], supplemented by Robinson's [2] further
decomposition of 296 — 1. If any more of these 'prime' factors should turn out to
be composite, doubt would be cast on the corresponding Pn . Mersenne polynomials
for n = 107 and 127 are also given. The prime x127 + x + 1 was found by Zier 1er
[3]. Its nature follows from the general result that if ?,anxn divides 2c„x" (mod p),
then
~Lanxv divides 2c„xp (modp).
The primitive character of each polynomial Pn(x) listed has been checked by a
repetition of the second and third stages on the conjugate polynomial x"P„(x~1).
In the list only the degrees of the separate terms in Pn are given, thus
127 1 0 stands for xm + x + 1.
Department of Mathematics
University of Manchester
1. M. Kraïtchik, Introduction à la Théorie des Nombres, Gauthier-Villars, Paris, 1952.
2. R. M. Robinson, "Some factorizations of numbers of the form 2" ± 1," MTAC, v. 11,
1957, p. 265-268.
3. N. Zierler, "Linear recurring sequences," /. Soc. Indust. Appl. Math., v. 7, 1959, p.
31-48.
Received December 18, 1961.
368
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use
PRIMITIVE POLYNOMIALS (MOD 2)
Primitive Polynomials (mod 2)
1 0
2 1 0
3 1 0
4 1 0
5 2 0
6
7
8
9
10
46
47
48
49
501 0
1 0
4 3
4 0
3 0
11 2 0
12 6 4 1 0
13 4 3 1 0
14 5 3 1 0
15 1 0
16 5 3 2
17 3 0
18 5 2 1
19 5 2 1
20 3 0
21 2 0
22 1 0
23 5 0
24 4 3 1
25 3 0
26 6 2 1
27 5 2 1
28 3 0
29 2 0
30 6 4 1
31 3 0
32 7 5 3
33 6 4 1
34 7 6 5
35 2 0
36 6 5
37 5 4
38 6 5
39 4 0
40 5 4 3
41 3 0
42 5 4 3
43 6 4 3
44 6 5 2
45 4 3 14 2 1
3 2 1
1 0
051
52
53
54
55
61
62
63
64
65
66
67
70
71
72
73
74
75
81
82
83
84
85
86
87
88
89
90
91
92
93
94
9576 5
77 6
78 7
79 4
80 72
5
0
3
3
6
2
5
5
3
3
4
3
4
3
96 7 6
97 6 0
98 7 4
99 7 5
100 8 756 7 4 2 0
57 5 3 2 0
58 6 5 1 0
59 6 5 4 3 1
60 1 0
0
0
0
0
3
0
0
0
0
0
2
0
0
0
4 2 0
5 2 0
2 1 0
3 2 0
107 7 5 3 2 1 0 127 1 0
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use