COMPUTING PRIMITIVE POLYNOMIALS

Examples and Test Cases

Sean E. O'Connor

Introduction

Here are a few examples and test cases which show the program output on various inputs. I omit printing the legal notice after the first example. I turn off the independent check that the polynomial is primitive after the first few runs, because it would take too long to finish (it's used for debugging.)

P is not prime

primpoly 138 3

Primpoly Version 5.3 - A Program for Computing Primitive Polynomials.
Copyright (C) 1999-2008 by Sean Erik O'Connor.  All Rights Reserved.

Primpoly comes with ABSOLUTELY NO WARRANTY; for details see the
GNU General Public License.  This is free software, and you are welcome
to redistribute it under certain conditions; see the GNU General Public License
for details.

p must be a prime number.

Primitive Polynomial of Degree 4 Modulo 2

$ primpoly -sc 2 4

Factoring r = 15 into
    3 5

Total number of primitive polynomials = 2.  Begin testing...

aabcdef

Primitive polynomial modulo 2 of degree 4

 x ^  4   +    x   +    1

+--------- Statistics ----------------------------
|
| Total num. degree  4 polynomials mod  2 :    16
|
| Actually tested :                              4
| a. Const. coeff. was primitive root :          2
| b. Free of linear factors :                    1
| c. Irreducible or irred. to power :            1
| d. Had order r (x^r = integer) :               1
| e. Passed const. coeff. test :                 1
| f. Had order m (x^m != integer) :              1
|
+-------------------------------------------------

Confirming polynomial is primitive with an independent check.
Warning:  You may wait an impossibly long time!

    -Polynomial is confirmed to be primitive.

Primitive Polynomial of Degree 5 Modulo 5

$ primpoly -s 5 5

Factoring r = 781 into
    11 71

Total number of primitive polynomials = 280.  Begin testing...

aaaaaaaaabcdef

Primitive polynomial modulo 5 of degree 5

 x ^  5   +    4 x   +    2

+--------- Statistics ----------------------------
|
| Total num. degree  5 polynomials mod  5 :    3125
|
| Actually tested :                             23
| a. Const. coeff. was primitive root :          9
| b. Free of linear factors :                    1
| c. Irreducible or irred. to power :            1
| d. Had order r (x^r = integer) :               1
| e. Passed const. coeff. test :                 1
| f. Had order m (x^m != integer) :              1
|
+-------------------------------------------------

Primitive Polynomial of Degree 55 Modulo 2

$ primpoly -s 2 55

Factoring r = 36028797018963967 into
    23 31 89 881 3191 201961

Total number of primitive polynomials = 598690870272000.  Begin testing...

aababaabaaababaaabaababaabaaabaababaaababaabaaababaaabcdef

Primitive polynomial modulo 2 of degree 55

 x ^ 55   +    x ^  6   +    x ^  2   +    x   +    1

+--------- Statistics ----------------------------
|
| Total num. degree 55 polynomials mod  2 :    36028797018963968
|
| Actually tested :                             72
| a. Const. coeff. was primitive root :         36
| b. Free of linear factors :                   18
| c. Irreducible or irred. to power :            1
| d. Had order r (x^r = integer) :               1
| e. Passed const. coeff. test :                 1
| f. Had order m (x^m != integer) :              1
|
+-------------------------------------------------

Degree 10 modulo 137 exceeds machine range

$ primpoly 137 10

ERROR:  p to the nth power must be smaller than 4294967295

Primitive Polynomial of Degree 8 Modulo 137.

$ primpoly -s 137 8

Factoring r = 912484779174120 into
    2^3 3 5 23 41 1409 1877 3049

Total number of primitive polynomials = 3627463779287040.  Begin testing...

abcdeabcdeabcdeababcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde
abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabc
deabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde
abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabc
deabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdef

Primitive polynomial modulo 137 of degree 8

 x ^  8   +    x   +    3

+--------- Statistics ----------------------------
|
| Total num. degree  8 polynomials mod 137 :    124097929967680321
|
| Actually tested :                            141
| a. Const. coeff. was primitive root :         66
| b. Free of linear factors :                   66
| c. Irreducible or irred. to power :           65
| d. Had order r (x^r = integer) :              65
| e. Passed const. coeff. test :                65
| f. Had order m (x^m != integer) :              1
|
+-------------------------------------------------

All primitive polynomials of degree 5 modulo 2.

primpoly -a  2 5

Total number of primitive polynomials = 6.  Begin testing...

Primitive polynomial 1 of 6 modulo 2 of degree 5

x ^  5   +    x ^  2   +    1

Primitive polynomial 2 of 6 modulo 2 of degree 5

x ^  5   +    x ^  3   +    1

Primitive polynomial 3 of 6 modulo 2 of degree 5

x ^  5   +    x ^  3   +    x ^  2   +    x   +    1

Primitive polynomial 4 of 6 modulo 2 of degree 5

x ^  5   +    x ^  4   +    x ^  2   +    x   +    1

Primitive polynomial 5 of 6 modulo 2 of degree 5

x ^  5   +    x ^  4   +    x ^  3   +    x   +    1

Primitive polynomial 6 of 6 modulo 2 of degree 5

x ^  5   +    x ^  4   +    x ^  3   +    x ^  2   +    1

Home