# COMPUTING PRIMITIVE POLYNOMIALS - USER MANUAL

### Introduction

Let's find a primitive polynomial of degree 4 modulo 2

$./Primpoly.exe 2 4 Primpoly Version 16.2 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2022 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. Self-check passes... Primitive polynomial modulo 2 of degree 4 x ^ 4 + x + 1, 2 We can also do higher moduli.$ ./Primpoly.exe 137 5 Primpoly Version 16.2 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2022 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. Self-check passes... Primitive polynomial modulo 137 of degree 5 x ^ 5 + x + 129, 137

You can also test a given polynomial for primitivity. Indicate the modulus after the comma.

./Primpoly.exe -t "x^4 + x + 1, 2" Primpoly Version 16.2 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2022 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. Self-check passes... x ^ 4 + x + 1, 2 is primitive!
./Primpoly.exe -t "x^4 + x^2 + 1, 2" Primpoly Version 16.2 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2022 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. Self-check passes... x ^ 4 + x ^ 2 + 1, 2 is NOT primitive!

#### Limits on the Size of the Prime p

The prime modulus p does have an upper bound, although a large one. p < 2m/2 - 1 where m = number of bits in the computer's integer type (defined in Primpoly.h). On most machines this will be 64 bits: p < 2147483648.

./Primpoly.exe 65003 2 Primpoly Version 16.2 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2022 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. Self-check passes... Primitive polynomial modulo 65003 of degree 2 x ^ 2 + x + 15, 65003

#### A Word about the Self-Check

We print out a self-check file in the same directory as Primpoly.exe called unitTest.log If the program fails, please send it to me to help diagnose any bugs.

Primpoly Version 16.2 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2022 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. Begin unit testing... TEST: Parsing command line options for test polynomial x^4 + 1, 2 with -s -t and -c options..........PASS! TEST: parsing constant 0.........PASS! TEST: parsing polynomial with a specified modulus: 2 x ^ 3 + 3 x + 4, 5.........PASS! TEST: parsing polynomial 2x without a modulus, which will be defaulted to p=2: 2x.........PASS! TEST: parsing bad syntax x 1.........PASS! TEST: BigInt switching from base = 2147483648 to new base = 10.........PASS! TEST: BigInt u default constructor which gives u = 0..........PASS! TEST: Constructor BigInt u( d ) from ppuint d = 1234.........PASS! TEST: Constructor BigInt u( s ) from string s = "1234".........PASS! TEST: Constructor BigInt u( s ) from INVALID string s = "12x34".........PASS! TEST: Copy constructor BigInt v( u ) from BigInt u( 123 ).........PASS! TEST: Assignment operator v = u from BigInt v and BigInt u( 123 ).........PASS! TEST: Implicit casting ppuint d = u from BigInt u( "01234" ).........PASS! TEST: Explicit casting static_cast< ppuint >( u ) from BigInt u( "01234" ).........PASS! TEST: Check overflow during ui = static_cast< ppuint >(u) on BigInt u( "3141592653589793238462643383279" ).........PASS! TEST: Stream output os << from BigInt u( "1234567890" ).........PASS! TEST: Stream input is >> u for BigInt u where we've loaded the stream is.str( "314159265358979323846264" ).........PASS! TEST: Equality test BigInt u == ppuint d?.........PASS! TEST: Equality test BigInt u == BigInt v.........PASS! TEST: BigInt u > BigInt v.........PASS! TEST: BigInt u( "1234" ) -= ppuint d.........PASS! TEST: BigInt u -= static_cast<ppuint>(5) underflow.........PASS! TEST: BigInt u += ppuint d.........PASS! TEST: BigInt v = BigInt u * ppuint d.........PASS! TEST: BigInt u /= ppuint d.........PASS! TEST: BigInt u /= ppuint d underflow to zero..........PASS! TEST: BigInt v = ++BigInt u.........PASS! TEST: BigInt v = --BigInt u.........PASS! TEST: BigInt++.........PASS! TEST: BigInt--.........PASS! TEST: one digit BigInt + ppuint.........PASS! TEST: two digit BigInt + ppuint.........PASS! TEST: BigInt + BigInt.........PASS! TEST: BigInt + BigInt.........PASS! TEST: BigInt - BigInt.........PASS! TEST: BigInt - BigInt < 0.........PASS! TEST: BigInt - ppuint.........PASS! TEST: one digit BigInt * BigInt.........PASS! TEST: two digit BigInt * BigInt.........PASS! TEST: BigInt multidigit *.........PASS! TEST: BigInt multidigit *=.........PASS! TEST: BigInt / BigInt one digit divisor..........PASS! TEST: BigInt / BigInt multidigit.........PASS! TEST: BigInt / BigInt leading zero digit..........PASS! TEST: BigInt / 0 .........PASS! TEST: BigInt % BigInt with u > v.........PASS! TEST: BigInt multidigit mod with normalizing constant d = 1.........PASS! TEST: BigInt % BigInt with u < v.........PASS! TEST: BigInt % ppuint = 314159 / 9 = 5 with ppuint < base .........PASS! TEST: BigInt % ppuint = 398765 % 3457u with ppuint > base overflow?.........PASS! TEST: BigInt / BigInt low probability if branch..........PASS! TEST: Switching back from base 10 to oldBase 2147483648.........PASS! TEST: Decimal string to BigInt conversion and back to decimal string using default base..........PASS! TEST: BigInt z = x * y then x =? z / y multidigit with default base..........PASS! TEST: BigInt testBit.........PASS! TEST: testBit().........PASS! TEST: BigInt power( ppuint 2, ppuint 100 ).........PASS! TEST: BigInt ceilLg( 6 ).........PASS! TEST: BigInt eval 2 ^ 1198 - 1 = 3 * 366994123 * 16659379034607403556537 * 148296291984475077955727317447564721950969097 * 8398047009001231954734680924979017504225305878286200635075545151446835102504\ 90874819119570309824866293030799718783 * 1884460498967805432001612672369307101507474835976431925948333387748670120353\ 629453261347843140212808570505767386771290423087216156597588216186445958479269565424431335013281 .........PASS! TEST: ModP 10 = 3 (mod 7).........PASS! TEST: ModP -10 = 4 (mod 7).........PASS! TEST: ModP( 0 ) throwing ArithModPException.........PASS! TEST: ppuint gcd( 85, 25 ) = 5.........PASS! TEST: BigInt gcd( 779953197883173551166308319545, 1282866356929526866866376009397 ) = 1.........PASS! TEST: c,r = addMod( a, b, n ) for ppuint type of 64 bits .........PASS! TEST: c,r = timesTwoMod( a, n ) for ppuint type of 64 bits .........PASS! TEST: c,r = multiplyMod( a, b, n ) for ppuint type of 64 bits .........PASS! TEST: PowerMod ppuint 3^10 = 4 (mod 7).........PASS! TEST: c,r = PowerMod( a, b ) modulo n for ppuint type of 64 bits .........PASS! TEST: PowerMod BigInt 3^10 = 4 (mod 7).........PASS! TEST: PowerMod with out of range inputs..........PASS! TEST: InverseModP 3 * 5 = 1 (mod 7).........PASS! TEST: IsPrimitiveRoot. 3 is a primitive root of 7..........PASS! TEST: IsPrimitiveRoot. 2 is a primitive root of 11..........PASS! TEST: IsPrimitiveRoot. 3 is NOT a primitive root of 11..........PASS! TEST: IsPrimitiveRoot. 5 is a primitive root of 65003..........PASS! TEST: IsPrimitiveRoot. 8 is NOT a primitive root of 65003..........PASS! TEST: constant coefficient test..........PASS! TEST: constant coefficient is primitive root..........PASS! TEST: isProbablyPrime on ppuint prime 97 with random x = 10.........PASS! TEST: isAlmostSurelyPrime for ppuint prime 97.........PASS! TEST: isAlmostSurelyPrime for BigInt prime 97.........PASS! TEST: isAlmostSurelyPrime for non-prime BigInt 49.........PASS! TEST: isAlmostSurelyPrime on the 10000th prime number 104729 of ppuint type.........PASS! TEST: Factor table method used on unsigned int 3^20 - 1 = 3486784400 = 2^4 5^2 11^2 61 1181.........PASS! TEST: Factor table method used on BigInt 3^20 - 1 = 3486784400 = 2^4 5^2 11^2 61 1181.........PASS! TEST: Trial division factoring on unsigned int 337500 = 2^2 3^3 5^5..........PASS! TEST: Trial division factoriing on BigInt 337500 = 2^2 3^3 5^5..........PASS! TEST: Pollard Rho factorization on unsigned int 25852 = 2^2 23 281.........PASS! TEST: Pollard Rho factorization on BigInt 25852 = 2^2 23 281.........PASS! TEST: BigInt computation of p^n, r, factors of r, EulerPhi[ p^n - 1]/n for p = 2.........PASS! TEST: Factor Copy constructor.........PASS! TEST: Factor assignment operator.........PASS! TEST: Polynomial() default constructor..........PASS! TEST: Polynomial() from string..........PASS! TEST: Polynomial = string..........PASS! TEST: Polynomial() from string with negative constant..........PASS! TEST: Polynomial() to string..........PASS! TEST: Polynomial() copy constructor..........PASS! TEST: Polynomial assignment operator..........PASS! TEST: Polynomial()[] read only operator..........PASS! TEST: Polynomial()[] accessing coeff higher than its degree..........PASS! TEST: Polynomial()[] lvalue operator..........PASS! TEST: Polynomial() += operator..........PASS! TEST: Polynomial() += operator..........PASS! TEST: Polynomial() + operator..........PASS! TEST: Polynomial * scalar.........PASS! TEST: Polynomial evaluation x^4 + 3x + 3 (mod 5).........PASS! TEST: Polynomial evaluation x^4 + x + 1 (mod 2).........PASS! TEST: Polynomial hasLinearFactor is true.........PASS! TEST: Polynomial hasLinearFactor is false.........PASS! TEST: Polynomial isInteger.........PASS!.........PASS! TEST: Polynomial initial and next trial polynomials.........PASS! TEST: PolyMod constructor from polynomials..........PASS! TEST: PolyMod constructor from string and polynomial..........PASS! TEST: PolyMod timesX..........PASS! TEST: PolyMod autoconvolve..........PASS! TEST: PolyMod convolve..........PASS! TEST: PolyMod coeffOfSquare..........PASS! TEST: PolyMod coeffOfProduct..........PASS! TEST: PolyMod square..........PASS! TEST: PolyMod operator* and implicitly, operator*=.........PASS! TEST: PolyMod x_to_power and isInteger().........PASS! TEST: PolyOrder reduced Q-I matrix.........PASS! TEST: PolyOrder 3 distinct factors out of 4.........PASS! TEST: PolyOrder, reducible polynomial x^3 + 3 mod 5 with 2 distinct factors.........PASS! TEST: PolyOrder, irreducible polynomial x^4 + x^2 + 2x + 3 mod 5 (nullity = 1).........PASS! TEST: PolyOrder 1 distinct factor 4 times.........PASS! TEST: PolyOrder order_m().........PASS! TEST: PolyOrder order_r() is true.........PASS! TEST: PolyOrder order_r() is false.........PASS! TEST: PolyOrder isPrimitive on non-primitive poly.........PASS! TEST: PolyOrder isPrimitive on primitive poly.........PASS! TEST: PolyOrder isPrimitive on primitive poly, part II.........PASS! End unit testing... CONGRATULATIONS! All tests passed!