Let's find a primitive polynomial of degree 4 modulo 2
Primpoly 2 4 Primpoly Version 10.4 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2009 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 10.4 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2009 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 -t "x^4 + x + 1, 2" Primpoly Version 10.4 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2009 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 -t "x^4 + x^2 + 1, 2" Primpoly Version 10.4 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2009 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!
Setting the print statistics flag -s on the command line shows the progress of the program while it is finding a primitive polynomial.
Primpoly -s 2 100 Primpoly Version 10.4 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2009 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 100 x ^ 100 + x ^ 8 + x ^ 7 + x ^ 2 + 1, 2 +--------- Statistics -------------------------------- | | Integer factorization: Trial division + Pollard Rho | | Number of trial divisions : 0 | Number of gcd's computed : 220 | Number of primality tests : 14 | Number of squarings: 207 | | Polynomial Testing | | Total num. degree 100 poly mod 2 : 1267650600228229401496703205376 | Number of possible primitive poly: 5707676340000000000000000000 | Polynomials tested : 390 | Const. coeff. was primitive root : 195 | Free of linear factors : 98 | Irreducible to power >=1 : 4 | Had order r (x^r = integer) : 3 | Passed const. coeff. test : 3 | Had order m (x^m != integer) : 1 | +-----------------------------------------------------
If the inputs are incorrect, the program will tell you.
Primpoly 138 5
Primpoly Version 10.4 - A Program for Computing Primitive Polynomials.
Copyright (C) 1999-2009 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: 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
Example: Primpoly 2 4 generates the fourth degree polynomial
x ^ 4 + x + 1, whose coefficients use modulo 2 arithmetic.
Primitive polynomials find many uses in mathematics and communications
engineering:
* Generation of pseudonoise (PN) sequences for spread spectrum
communications and chip fault testing.
* Generation of CRC and Hamming codes.
* Generation of Galois (finite) fields for use in decoding Reed-Solomon
and BCH error correcting codes.
Primpoly 1 1 Primpoly Version 10.4 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2009 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: ERROR: p must be 2 or more.
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.
Primpoly -c 2 4 Primpoly Version 10.4 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2009 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! x ^ 4 + x + 1, 2 confirmed primitive!
To find and list all primitive polynomials, use the -a flag.
Primpoly -a 2 4 Primpoly Version 10.4 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2009 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 Primitive polynomial modulo 2 of degree 4 x ^ 4 + x ^ 3 + 1, 2
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 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 ⌉
They are p ≥ 2, n ≥ 2.
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.
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.
The basic bounds are p ≤ 2, n ≥ 2 and pn ≤ MAXPTON All other bounds are derived from these.
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.
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.
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.
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().
Here are the classes which make up the program.
The BigInt class does arbitrary size non-negative integer arithmetic.
The Polynomial class does basic mod p polynomial arithmetic.
Parser converts polynomials to and from strings. It also parses command line arguments.
PolyMod does polynomial arithmetic modulo f(x) and p.
Exception classes throw exceptions for BigInt and Polynomial classes.
Copyright © 1986-2009 by Sean Erik O'Connor. All Rights Reserved. last updated 01 Jan 09.
Home
Up