COMPUTING PRIMITIVE POLYNOMIALS - USER MANUAL

Sean E. O'Connor

Introduction

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

$ ./Primpoly.exe 2 4 Primpoly Version 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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!

Factor Tables

You'll need to have the factor tables in the same directory as the executable. And you need to run the executable from that directory or else the self-check will fail:

seanoconnor:~/PrimitivePolynomials/Project/Build/Bin$ ls Primpoly.exe* c02minus.txt* c03minus.txt* c05minus.txt* c07minus.txt* c11minus.txt* seanoconnor:~/PrimitivePolynomials/Project/Build/Bin$ ./Primpoly.exe 2 4 Primpoly Version 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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 seanoconnor:~/PrimitivePolynomials/Project/Build/Bin$ cd .. seanoconnor:~/PrimitivePolynomials/Project/Build$ Bin/Primpoly.exe 2 4 Primpoly Version 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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. Error: Self-check failed! Please email the author at seanerikoconnor!AT!gmail!DOT!com with !DOT! replaced by . and the !AT! replaced by @ and attach the unitTest.log file which should be located in the current directory and all console output from this program. Thanks for your help. Best Wishes, Sean.

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 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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 * 839804700900123195473468092497901750422530587828620063507554515144683510250490874819119570309824866293030799718783 * 1884460498967805432001612672369307101507474835976431925948333387748670120353629453261347843140212808570505767386771290423087216156597588216186445958479269565424431335013281 .........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!

Additional Program Settings

Setting the print statistics flag -s on the command line shows the progress of the program while it is finding a primitive polynomial.

$ ./Primpoly.exe -s 200 Primpoly Version 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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... Inputs are incorrect or out of range: ERROR: Expecting two arguments, p and n. This program generates a primitive polynomial of degree n modulo p. Usage: Primpoly p n where p is a prime >= 2 and n is an integer >= 2 Primpoly -t <Polynomial to test>, p If you leave off the ,p we default to p = 2 Primpoly -a p n Same, but list all primitive polynomials of degree n mod p Primpoly -s p n Same, but print search statistics too. Primpoly -h Print this help message. Examples: Primpoly 2 4 Self-check passes... Primitive polynomial modulo 2 of degree 4 x ^ 4 + x + 1, 2 Primpoly -t x^4 + x + 1, 2 Self-check passes... x ^ 4 + x + 1, 2 is primitive! Primpoly -a 2 4 Self-check passes... Primitive polynomial modulo 2 of degree 4 x ^ 4 + x + 1, 2 Primitive polynomial modulo 2 of degree 4 x ^ 4 + x ^ 3 + 1, 2 Primpoly.exe -s 13 19 Self-check passes... Primitive polynomial modulo 13 of degree 19 x ^ 19 + 9 x + 2, 13 +--------- OperationCount -------------------------------- | | Integer factorization: Table lookup + Trial division + Pollard Rho | | Number of trial divisions : 0 | Number of gcd's computed : 9027 | Number of primality tests : 2 | Number of squarings: 9026 | | Polynomial Testing | | Total num. degree 19 poly mod 13 : 1461920290375446110677 | Number of possible primitive poly: 6411930599771980992 | Polynomials tested : 120 | Const. coeff. was primitive root : 46 | Free of linear factors : 11 | Irreducible to power >=1 : 1 | Had order r (x^r = integer) : 1 | Passed const. coeff. test : 1 | Had order m (x^m != integer) : 1 | +----------------------------------------------------- Primitive polynomials find many uses in mathematics and communications engineering: * Generation of pseudonoise (PN) sequences for spread spectrum communications and chip fault testing. * Generating Sobol sequences for high dimensional numerical integration. * Generation of CRC and Hamming codes. * Generation of Galois (finite) fields for use in decoding Reed-Solomon and BCH error correcting codes. For detailed technical information, see my web page http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html

If the inputs are incorrect, the program will tell you, and give you a big lecture.

seanoconnor:~/Desktop/Sean/WebSite/Mathematics/AbstractAlgebra/PrimitivePolynomials/Project/Build/Bin$ ./Primpoly.exe 138 5 Primpoly Version 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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... Inputs are incorrect or out of range: ERROR: p must be a prime number. This program generates a primitive polynomial of degree n modulo p. Usage: Primpoly p n where p is a prime >= 2 and n is an integer >= 2 Primpoly -t <Polynomial to test>, p If you leave off the ,p we default to p = 2 Primpoly -a p n Same, but list all primitive polynomials of degree n mod p Primpoly -s p n Same, but print search statistics too. Primpoly -h Print this help message. Examples: Primpoly 2 4 Self-check passes... Primitive polynomial modulo 2 of degree 4 x ^ 4 + x + 1, 2 Primpoly -t x^4 + x + 1, 2 Self-check passes... x ^ 4 + x + 1, 2 is primitive! Primpoly -a 2 4 Self-check passes... Primitive polynomial modulo 2 of degree 4 x ^ 4 + x + 1, 2 Primitive polynomial modulo 2 of degree 4 x ^ 4 + x ^ 3 + 1, 2 Primpoly.exe -s 13 19 Self-check passes... Primitive polynomial modulo 13 of degree 19 x ^ 19 + 9 x + 2, 13 +--------- OperationCount -------------------------------- | | Integer factorization: Table lookup + Trial division + Pollard Rho | | Number of trial divisions : 0 | Number of gcd's computed : 9027 | Number of primality tests : 2 | Number of squarings: 9026 | | Polynomial Testing | | Total num. degree 19 poly mod 13 : 1461920290375446110677 | Number of possible primitive poly: 6411930599771980992 | Polynomials tested : 120 | Const. coeff. was primitive root : 46 | Free of linear factors : 11 | Irreducible to power >=1 : 1 | Had order r (x^r = integer) : 1 | Passed const. coeff. test : 1 | Had order m (x^m != integer) : 1 | +----------------------------------------------------- Primitive polynomials find many uses in mathematics and communications engineering: * Generation of pseudonoise (PN) sequences for spread spectrum communications and chip fault testing. * Generating Sobol sequences for high dimensional numerical integration. * Generation of CRC and Hamming codes. * Generation of Galois (finite) fields for use in decoding Reed-Solomon and BCH error correcting codes. For detailed technical information, see my web page http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html seanoconnor:~/Desktop/Sean/WebSite/Mathematics/AbstractAlgebra/PrimitivePolynomials/Project/Build/Bin$

Setting check flag -c on the command line runs an independent check on the primitive polynomial after it is found to confirm it is primitive. Default is off, because this test can take practically forever for large values of pn: using the definition of primitive polynomial, we simply check xk(mod f(x), p) is not equal to 1 for 1 ≤ k ≤ pn-2, but that xk(mod f(x), p) = 1 for k = pn - 1. This flag is useful for debugging purposes.

seanoconnor:~/Desktop/Sean/WebSite/Mathematics/AbstractAlgebra/PrimitivePolynomials/Project/Build/Bin$ ./Primpoly.exe -c 2 4 Primpoly Version 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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 Confirming polynomial is primitive with an independent check. Warning: You may wait an impossibly long time! If you lose patience, you can hit control-C in your console window to stop this program. x ^ 4 + x + 1, 2 confirmed primitive!

To find and list all primitive polynomials, use the -a flag.

./Primpoly.exe -a 2 4 Primpoly Version 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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... There are 2 primitive polynomials modulo 2 of degree 4 Primitive polynomial modulo 2 of degree 4 x ^ 4 + x + 1, 2 Primitive polynomial modulo 2 of degree 4 x ^ 4 + x ^ 3 + 1, 2

Multiple Precision Integer Arithmetic C++ version

The object oriented C++ version has no limit to on the degree of the polynomial, except system memory, though it will slow down for very high degree.

The size of p is limited by the size of the base we use for multiple precision arithmetic which in turn depends on the native integer word size. If you run the program with a value of p larger than we can handle, you get an error message:

./Primpoly.exe 948903284092384092384 2 Primpoly Version 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2017 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... Inputs are incorrect or out of range: Error. Polynomial modulus p must be < 2147483648 This program generates a primitive polynomial of degree n modulo p. Usage: Primpoly p n where p is a prime >= 2 and n is an integer >= 2 Primpoly -t <Polynomial to test>, p If you leave off the ,p we default to p = 2 Primpoly -a p n Same, but list all primitive polynomials of degree n mod p Primpoly -s p n Same, but print search statistics too. Primpoly -h Print this help message. Examples: Primpoly 2 4 Self-check passes... Primitive polynomial modulo 2 of degree 4 x ^ 4 + x + 1, 2 Primpoly -t x^4 + x + 1, 2 Self-check passes... x ^ 4 + x + 1, 2 is primitive! Primpoly -a 2 4 Self-check passes... Primitive polynomial modulo 2 of degree 4 x ^ 4 + x + 1, 2 Primitive polynomial modulo 2 of degree 4 x ^ 4 + x ^ 3 + 1, 2 Primpoly.exe -s 13 19 Self-check passes... Primitive polynomial modulo 13 of degree 19 x ^ 19 + 9 x + 2, 13 +--------- OperationCount -------------------------------- | | Integer factorization: Table lookup + Trial division + Pollard Rho | | Number of trial divisions : 0 | Number of gcd's computed : 9027 | Number of primality tests : 2 | Number of squarings: 9026 | | Polynomial Testing | | Total num. degree 19 poly mod 13 : 1461920290375446110677 | Number of possible primitive poly: 6411930599771980992 | Polynomials tested : 120 | Const. coeff. was primitive root : 46 | Free of linear factors : 11 | Irreducible to power >=1 : 1 | Had order r (x^r = integer) : 1 | Passed const. coeff. test : 1 | Had order m (x^m != integer) : 1 | +----------------------------------------------------- Primitive polynomials find many uses in mathematics and communications engineering: * Generation of pseudonoise (PN) sequences for spread spectrum communications and chip fault testing. * Generating Sobol sequences for high dimensional numerical integration. * Generation of CRC and Hamming codes. * Generation of Galois (finite) fields for use in decoding Reed-Solomon and BCH error correcting codes. For detailed technical information, see my web page http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html

The largest integer which needs to be computed anywhere in the program is pn. Variables in the program which require extra precision are defined to be of BigInt type. Our multiple precision integer arithmetic is for unsigned numbers only, and is taken from Knuth's book:

D. E. Knuth, THE ART OF COMPUTER PROGRAMMING, VOL. 2, 3rd ed., Addison-Wesley, 1981, pgs. 250-265. Errata for Volume 2:

Given p and n, we can find the maximum number of digits m and base b.

First, the base b. Let N = number of bits in an integer type which we will use for our digits. The maximum unsigned integer is 2N-1. The largest number which is computed in the multiple precision integer arithmetic algorithms is b2. So if we let b = 2N/2 - 1, we'll guarantee b2 < 2N-1. and b will be a power of 2, an N/2 digit binary number, which is needed to efficiently implement shifting and masking operations.

The maximum integer which needs to be computed is pn = bm - 1. So pn + 1 = bm. A bound is then pn < bm, or n lg p < m lg b or (n lg p) / (lg b) < m or m = ⌈ (n lg p) / lg b ⌉

Lower Bounds for pn

They are p ≥ 2, n ≥ 2.

Limit on the Sizes of p and n: C Version

Since we use the system hardware integer arithmetic, there are internal limits within program which restrict the size of the largest primitive polynomial which may be computed. We discuss bounds on various internal integer variables below. Most bounds are set in the source file pp.h and tested in pp.c.

Upper Bound on Size of Internal Integer Computations

The largest integer which needs to be computed anywhere in the program is pn. Variables in the program which require this extra precision are defined to be of Bigint type.

This should be an unsigned integer type, since all computations with Bigint involve multiplication, division, modulo, masking and decrement by 1, so we don't use negative numbers. The alternative is to use a signed integer type, but reduce the number of bits used by 1, to avoid overflowing into the sign bit.

For the Windows/Intel platform, the largest integer type in the Microsoft Visual C++ 6.0 SP3 compiler is the signed 64-bit __int64. For a Mac OS X, PC/cygwin or other Unix platform which uses the GNU C compiler 4.0, we use the 64-bit long long type. We play it safe and assume this is also a signed type. Thus we need to set the maximum size of pn to 264-1-1. So, for example, when p = 2, the highest polynomial degree is n = 62.

A Bound for pn (MAXPTON)

The basic bounds are p ≤ 2, n ≥ 2 and pn ≤ MAXPTON All other bounds are derived from these.

A Bound for r

r = (pn - 1) / (p - 1) so the upper bound is r (pn - 1) / (2 - 1) = pn - 1 ≤ pn ≤ MAXPTON. And the lower bound is r = pn-1 + pn-2 + ... + p + 1 ≥ p + 1 ≥ 3.

A Bound for the Number of Prime Factors (MAXNUMPRIMEFACTORS)

This is used for sizing the array containing the prime factors of r and their multiplicities. r = p1e1 ... pkek ≥ 2 ... 2 = 2k. r = p1 ... pk ≥ 2 ... 2 = 2k. Since the pi ≥ 2 are primes. Since r ≥ 3 from above, we must have at least one prime factor, and so k ≥ 1. Thus 2k ≤ r or k ≤ lg r where lg is log2. Then k ≤ lg MAXPTON. We need an integer value for the upper bound, so we play it safe and round up to MAXNUMPRIMEFACTORS = 1 + floor( lg MAXPTON ).

This is also used for the array containing the prime factors of p-1. As above, the maximum number of prime factors of p-1 < max. num. prime factors of p < < max. num. prime factors of pn. So the upper bound above should work fine.

A Bound for n. (MAXDEGPOLY)

2n ≤ pn ≤ MAXPTON, so n ≤ lg MAXPTON. Again, to play it safe, we chop this bound to MAXDEGPOLY = floor( lg MAXPTON ). The bound is exact when p = 2.

Number of trials for probabilistic primality testing. (NUM_PRIME_TEST_TRIALS)

We error check the input parameter p, to see if it is prime. Our probabilistic primality test has the failure probabilities, P( test says p is not prime | p is prime ) ≤ (1/4)NUM_PRIME_TEST_TRIALS. Defaulted to 25. The test always succeeds in detecting if p is composite (non-prime). This depends somewhat on the quality of the system random number generator, rand().


Copyright © 1986-2017 by Sean Erik O'Connor. All Rights Reserved.     last updated 01 Jan 17.