Finding Primitive Polynomials¶
LEGAL
PrimpolySageMath Version 16.2 - A Program for Computing Primitive Polynomials using Sage Math.
Copyright (C) 1999-2024 by Sean Erik O'Connor. All Rights Reserved.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/.
The author's address is seanerikoconnor!AT!gmail!DOT!com
with the !DOT! replaced by . and the !AT! replaced by @This notebook is called PrimpolySageMath.ipynb¶
Run it using
jupyter lab PrimpolySageMath.ipynb
When you get done, please create an HTML version of this notebook for viewing on the web by running
jupyter nbconvert PrimpolySageMath.ipynb --to html
I urge you to do Kernel->Restart Kernel and Clear All Outputs , followed by Kernel->Restart Kernel and Run All Cells
Counting the number of primitive polynomials of degree n modulo p. The probability that a polynomial chosen at random is primitive.¶
In [1]:
def numPolynomials(p,n):
""""The total number of polynomials of degree n modulo p."""
return p ^ n
In [2]:
def numPrimitivePolynomials(p,n):
""""The number of primitive polynomials of degree n modulo p."""
return euler_phi( p ^ n - 1 ) / n
In [3]:
def probabilityRandomPolynomialIsPrimitive(p,n):
""""Probability that a polynomial of degree n modulo p chosen at random is primitive."""
return numPrimitivePolynomials( p, n ) / numPolynomials( p, n )
Let's do a low degree example with a small modulus.¶
In [4]:
p = 5 ; n = 4
In [5]:
numPolynomials(p,n)
Out[5]:
625
In [6]:
numPrimitivePolynomials(p,n)
Out[6]:
48
In [7]:
N(probabilityRandomPolynomialIsPrimitive(p,n),digits=3)
Out[7]:
0.0768
Testing whether a is a primitive root of p¶
In [8]:
def isPrimRoot(a,p):
"""If the smallest n for which a^n = 1 is p-1, then a is a primitive root of p."""
if Mod(a,p) == 0:
return False
elif Mod(a,p).multiplicative_order() == p-1:
return True
else:
return False
In [9]:
isPrimRoot(3,p)
Out[9]:
True
Since 3 is a primitive root of 5, it generates the nonzero elements of GF(5).¶
In [10]:
[Mod(3^i,p) for i in range(1,p)]
Out[10]:
[3, 4, 2, 1]
But 4 is not a primitive root of 5 since its order is only 2 instead of 4.¶
In [11]:
[Mod(4^i,p) for i in range(1,p)]
Out[11]:
[4, 1, 4, 1]
In [12]:
Mod(4,p).multiplicative_order()
Out[12]:
2
Define the ring of polynomials with coefficients over GF(p) with generator x.¶
In [13]:
R.<x>=PolynomialRing(GF(p))
In [14]:
R
Out[14]:
Univariate Polynomial Ring in x over Finite Field of size 5
Testing if polynomials have linear factors.¶
In [15]:
def numPolynomialsWithLinearFactors(p,n):
""""The number of polynomials of degree n modulo p which have one or more linear factors."""
if n >= p:
return p^n - ((p-1)^p) * p^(n-p)
else:
var('i') # Define i to be a symbolic variable.
return sum( -((-1)^i) * binomial( p, i ) * p^(n-i), i, 1, n)
In [16]:
def probRandomPolyHasLinearFactors(p,n):
"""" The probability that a polynomial of degree n modulo p has one or more linear factors."""
if n >= p:
return 1 - (1 - 1 / p)^p
else:
return numPolynomialsWithLinearFactors(p,n) / (p^n)
In [17]:
def polynomialHasLinearFactor(f):
"""" A test whether a polynomial of degree n modulo p has one or more linear factors."""
hasRoot=false
for i in range(0,p):
if f(i) == 0:
return True
return False
An example polynomial of low degree.¶
In [18]:
f = x^4 + x^2 + 2*x + 3 ; pretty_print(f)
\(\displaystyle x^{4} + x^{2} + 2 x + 3\)
In [19]:
numPolynomialsWithLinearFactors(p,n)
Out[19]:
420
In [20]:
N(probRandomPolyHasLinearFactors(p,n),digits=3)
Out[20]:
0.672
In [21]:
polynomialHasLinearFactor(f)
Out[21]:
False
Confirm that f has no linear factors.¶
In [22]:
[f(k) for k in range(0,p)]
Out[22]:
[3, 2, 2, 4, 3]
Confirm that this polynomial with two roots, i.e. two linear factors, does indeed pass the one or more linear factors test.¶
In [23]:
polynomialHasLinearFactor((x-2)*(x-3))
Out[23]:
True
Testing if a polynomial is constant¶
In [24]:
def isConstantPolynomial(f):
"""Is the polynomial constant?"""
# Get the polynomial coefficients and their number. For example, if
# f = x^4 + x^2 + 2*x + 3
# then f.list() = [3, 2, 1, 0, 1] and f.list()[0] = 3
coeffList = f.list()
numCoeff = len( coeffList )
# Polynomial has only a constant term.
if numCoeff == 1:
return True
else:
# Otherwise, do the powers x, x^2, ... have even one nonzero coefficient?
hasNonZeroPowers = False
for k in range(1, numCoeff):
if coeffList[ k ] != 0:
hasNonZeroPowers = True
break
# Nope, coefficients of the powers x, x^2, ... are all zero; polynomial is a constant.
return not hasNonZeroPowers
In [25]:
help(isConstantPolynomial)
Help on function isConstantPolynomial in module __main__:
isConstantPolynomial(f)
Is the polynomial constant?
In [26]:
isConstantPolynomial( f )
Out[26]:
False
In [27]:
isConstantPolynomial(3)
Out[27]:
True
In [28]:
Q.<z>=R.quotient( f )
In [29]:
Q
Out[29]:
Univariate Quotient Polynomial Ring in z over Finite Field of size 5 with modulus x^4 + x^2 + 2*x + 3
Powers of z modulo f(x) and p¶
In [30]:
def powersOfXModfp(f,n,p):
"""Compute the powers {z^0, z^p, z^2p, ..., z^(np)} modulo f(x) and p."""
# Locally define the quotient ring Q of polynomials modulo f(x) and p.
R.<x>=PolynomialRing(GF(p))
Q.<z>=R.quotient( f )
# Return the list of all powers.
return [z ^ (p * k) for k in range(0,n)]
In [31]:
listOfPowers = powersOfXModfp(f,n,p) ; pretty_print( listOfPowers )
\(\displaystyle \left[1, 4 z^{3} + 3 z^{2} + 2 z, z^{3} + 4 z^{2} + 3, 3 z^{3} + 4 z^{2} + 4 z\right]\)
Irreducibility Testing¶
Compute Q-I where the n rows of matrix Q are the coefficients of the powers z^0, z^p, ..., z^(np) mod f(x) and p.¶
In [32]:
def generateQIMatrix(f,n,p):
"""Generate the Q - I matrix. Rows of Q are coefficients of the powers z^0, ..., z^(np) modulo f(x), p"""
# Locally define the quotient ring Q of polynomials modulo f(x) and p.
R.<x>=PolynomialRing(GF(p))
Q.<z>=R.quotient( f )
# Compute the powers {z^0, z^p, z^2p, ..., z^(np)} modulo f(x) and p.
# e.g. for f = x^4 + x^2 + 2*x + 3 modulo p=5,
# listOfPowers = [1, 4*z^3 + 3*z^2 + 2*z, z^3 + 4*z^2 + 3, 3*z^3 + 4*z^2 + 4*z]
listOfPowers = powersOfXModfp(f,n,p)
# e.g. row 1 is listOfPowers[1].list() = [0, 2, 3, 4]
rows = [listOfPowers[k].list() for k in range(0,n)]
# Define a matrix space of n x n matrices modulo p.
M = MatrixSpace(GF(p),n,n)
# Load the rows.
m = M.matrix( rows )
# Q-I
return m - matrix.identity(n)
In [33]:
m = generateQIMatrix(f,n,p) ; pretty_print( m )
\(\displaystyle \left(\begin{array}{rrrr}
0 & 0 & 0 & 0 \\
0 & 1 & 3 & 4 \\
3 & 0 & 3 & 1 \\
0 & 4 & 4 & 2
\end{array}\right)\)
This is the left kernel, i.e. all vectors w satisfying w A = 0¶
In [34]:
k = kernel(m) ; k
Out[34]:
Vector space of degree 4 and dimension 1 over Finite Field of size 5 Basis matrix: [1 0 0 0]
In [35]:
m.left_nullity()
Out[35]:
1
In [36]:
def hasTwoOrMoreDistinctIrreducibleFactors(f,n,p):
m=generateQIMatrix(f,n,p)
return m.left_nullity() >= 2
In [37]:
hasTwoOrMoreDistinctIrreducibleFactors(f,n,p)
Out[37]:
False
Factor the expression r into distinct primes.¶
If you interrupt the kernel while factoring, you can see that SageMath uses [https://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#se:factorint](PARI's integer factorization) which uses the following methods:
- Factors the integer n into a product of pseudoprimes (see ispseudoprime), using a combination of the Shanks SQUFOF and Pollard Rho method (with modifications due to Brent), Lenstra's ECM (with modifications by Montgomery), and MPQS (the latter adapted from the LiDIA code with the kind permission of the LiDIA maintainers), as well as a search for pure powers.
In [38]:
r=(p^n-1)//(p-1) ; r
Out[38]:
156
In [39]:
factorization = factor(r) ; pretty_print( factorization )
\(\displaystyle 2^{2} \cdot 3 \cdot 13\)
In [40]:
# p = 2 ; n = 929 ; r=(p^n-1)//(p-1) ; pretty_print( r )
# factorization = factor(r) ; pretty_print( factorization )
NOTE: Use // for integer divide instead of / or else we'll get a rational number type for the answer even if (p-1) divides (p^n-1).¶
In [41]:
type( 156 / 4 )
Out[41]:
<class 'sage.rings.rational.Rational'>
In [42]:
type( 156 // 4 )
Out[42]:
<class 'sage.rings.integer.Integer'>
Distinct prime factors of r¶
In [43]:
def distinctPrimeFactors(r):
# Factorization object. e.g. for r = 156, factor(r) = 2^2 * 3 * 13
factorization = factor(r)
# List of prime factors to powers. e.g. list(factor(r)) = [(2, 2), (3, 1), (13, 1)]
listOfPrimesToPowers = list(factorization)
# Pull out the prime factors only. e.g. [2, 3, 13]
distinctPrimeFactors = [listOfPrimesToPowers[k][0] \
for k in range(0,len(listOfPrimesToPowers))]
return distinctPrimeFactors
In [44]:
distinctPrimeFactors(r)
Out[44]:
[2, 3, 13]
Testing whether a polynomial f(x) modulo p is primitive.¶
In [45]:
def isPrimitivePolynomial( f, n, p ):
"""Determine if the nth degree polynomial f(x) modulo p is primitive."""
isPrimitive = False
# Polynomial must be at least degree 2 modulo p >= 2
if p < 2 or n < 2:
return False
print( f"Passed step 1: p={p:d} >=2 and n = {n} >= 2")
a0=f[0]
if isPrimRoot( a0 * (-1)^n, p ):
print( f"Passed step 2: a0 = {a0} is a primitive root")
if not polynomialHasLinearFactor(f):
print( f"Passed step 3: f(x) = {f} has no linear factors" )
if not hasTwoOrMoreDistinctIrreducibleFactors(f,n,p):
print( f"Passed step 4: f(x) = {f} is either irreducible or irreducible ^ power" )
R.<x>=PolynomialRing(GF(p))
Q.<z>=R.quotient( f )
r=(p^n-1)//(p-1)
a=z^r
if isConstantPolynomial(a):
print( f"Passed step 5: a = {a} is constant" )
if a == Mod( a0 * (-1)^n, p):
print( f"Passed step 6: a = a0 (-1)^n mod p where a0 = {a0}" )
# Tentatively say it's primitive.
isPrimitive = True
primes = distinctPrimeFactors(r)
print( f"Begin step 7: Testing on prime factors p{0} ... p{len(primes)-1}" )
for k in range( 0 , len( primes )):
# Skip the test for kth prime pk if (p-1) | pk
if Mod( (p-1), primes[k] ) == 0:
print( f" Skip step 7 test since prime p{k} = {primes[k]} divides p-1 = {p-1}")
else:
# Oops! Failed the test for prime pk.
if isConstantPolynomial( z^(r//primes[k]) ):
print( f" Failed step 7 since x^m is an integer for prime p{k} = {primes[k]}")
isPrimitive = False
else:
print( f" Passed step 7 since x^m is not an integer for prime p{k} = \
{primes[k]}")
return isPrimitive
Examples: Primitive and non-primitive polynomials as generators of field elements.¶
A primitive polynomial generates all of the p^n - 1 nonzero field elements.¶
In [46]:
p = 5 ; n = 4
In [47]:
f = x^4 + x^2 + 2*x + 2 ; pretty_print( f )
\(\displaystyle x^{4} + x^{2} + 2 x + 2\)
In [48]:
isPrimitivePolynomial( f, n, p )
Passed step 1: p=5 >=2 and n = 4 >= 2 Passed step 2: a0 = 2 is a primitive root Passed step 3: f(x) = x^4 + x^2 + 2*x + 2 has no linear factors Passed step 4: f(x) = x^4 + x^2 + 2*x + 2 is either irreducible or irreducible ^ power Passed step 5: a = 2 is constant Passed step 6: a = a0 (-1)^n mod p where a0 = 2 Begin step 7: Testing on prime factors p0 ... p2 Skip step 7 test since prime p0 = 2 divides p-1 = 4 Passed step 7 since x^m is not an integer for prime p1 = 3 Passed step 7 since x^m is not an integer for prime p2 = 13
Out[48]:
True
In [49]:
def generateAllNonzeroFieldElements( f, n, p ):
"""Generate all the nonzero finite field elements for GF(p^n) given polynomial f(x),
which is not necessarily primitive."""
# Define the quotient ring Q of polynomials modulo f(x) and p.
R.<x>=PolynomialRing(GF(p))
Q.<z>=R.quotient( f )
# A primitive polynomial f generates the nonzero elements of the field:
# z^m = 1 for m = p^n - 1 but z^m != 1 for 1 <= m <= p^n - 2
fieldElements = [z^m for m in range(1,p^n)]
return fieldElements
In [50]:
fieldElements = generateAllNonzeroFieldElements( f, n, p ) ; pretty_print( fieldElements )
\(\displaystyle \left[z, z^{2}, z^{3}, 4 z^{2} + 3 z + 3, 4 z^{3} + 3 z^{2} + 3 z, 3 z^{3} + 4 z^{2} + 2 z + 2, 4 z^{3} + 4 z^{2} + z + 4, 4 z^{3} + 2 z^{2} + z + 2, 2 z^{3} + 2 z^{2} + 4 z + 2, 2 z^{3} + 2 z^{2} + 3 z + 1, 2 z^{3} + z^{2} + 2 z + 1, z^{3} + 2 z + 1, z^{2} + 4 z + 3, z^{3} + 4 z^{2} + 3 z, 4 z^{3} + 2 z^{2} + 3 z + 3, 2 z^{3} + 4 z^{2} + 2, 4 z^{3} + 3 z^{2} + 3 z + 1, 3 z^{3} + 4 z^{2} + 3 z + 2, 4 z^{3} + z + 4, 2 z^{2} + z + 2, 2 z^{3} + z^{2} + 2 z, z^{3} + z + 1, 4 z + 3, 4 z^{2} + 3 z, 4 z^{3} + 3 z^{2}, 3 z^{3} + z^{2} + 2 z + 2, z^{3} + 4 z^{2} + z + 4, 4 z^{3} + 2 z + 3, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4 z + 4, 4 z^{3} + 4 z^{2} + 4 z, 4 z^{3} + 2 z + 2, 3 z^{2} + 4 z + 2, 3 z^{3} + 4 z^{2} + 2 z, 4 z^{3} + 4 z^{2} + 4 z + 4, 4 z^{3} + z + 2, 2 z^{2} + 4 z + 2, 2 z^{3} + 4 z^{2} + 2 z, 4 z^{3} + z + 1, 2 z^{2} + 3 z + 2, 2 z^{3} + 3 z^{2} + 2 z, 3 z^{3} + z + 1, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4 z + 4, z^{3} + 4 z^{2} + 4 z, 4 z^{3} + 3 z^{2} + 3 z + 3, 3 z^{3} + 4 z^{2} + 2, 4 z^{3} + 2 z^{2} + z + 4, 2 z^{3} + 2 z^{2} + z + 2, 2 z^{3} + 4 z^{2} + 3 z + 1, 4 z^{3} + z^{2} + 2 z + 1, z^{3} + 3 z^{2} + 3 z + 2, 3 z^{3} + 2 z^{2} + 3, 2 z^{3} + 2 z^{2} + 2 z + 4, 2 z^{3} + 1, 3 z^{2} + 2 z + 1, 3 z^{3} + 2 z^{2} + z, 2 z^{3} + 3 z^{2} + 4 z + 4, 3 z^{3} + 2 z^{2} + 1, 2 z^{3} + 2 z^{2} + 4, 2 z^{3} + 3 z^{2} + 1, 3 z^{3} + 3 z^{2} + 2 z + 1, 3 z^{3} + 4 z^{2} + 4, 4 z^{3} + 2 z^{2} + 3 z + 4, 2 z^{3} + 4 z^{2} + z + 2, 4 z^{3} + 4 z^{2} + 3 z + 1, 4 z^{3} + 4 z^{2} + 3 z + 2, 4 z^{3} + 4 z^{2} + 4 z + 2, 4 z^{3} + 4 z + 2, 4 z + 2, 4 z^{2} + 2 z, 4 z^{3} + 2 z^{2}, 2 z^{3} + z^{2} + 2 z + 2, z^{3} + 3 z + 1, 2 z^{2} + 4 z + 3, 2 z^{3} + 4 z^{2} + 3 z, 4 z^{3} + z^{2} + z + 1, z^{3} + 2 z^{2} + 3 z + 2, 2 z^{3} + 2 z^{2} + 3, 2 z^{3} + 3 z^{2} + 4 z + 1, 3 z^{3} + 2 z^{2} + 2 z + 1, 2 z^{3} + 4 z^{2} + 4, 4 z^{3} + 3 z^{2} + 1, 3 z^{3} + z^{2} + 3 z + 2, z^{3} + z + 4, 2 z + 3, 2 z^{2} + 3 z, 2 z^{3} + 3 z^{2}, 3 z^{3} + 3 z^{2} + z + 1, 3 z^{3} + 3 z^{2} + 4, 3 z^{3} + 2 z^{2} + 3 z + 4, 2 z^{3} + 3 z + 4, z^{2} + 1, z^{3} + z, 3 z + 3, 3 z^{2} + 3 z, 3 z^{3} + 3 z^{2}, 3 z^{3} + 2 z^{2} + 4 z + 4, 2 z^{3} + z^{2} + 3 z + 4, z^{3} + z^{2} + 1, z^{3} + 4 z^{2} + 4 z + 3, 4 z^{3} + 3 z^{2} + z + 3, 3 z^{3} + 2 z^{2} + 2, 2 z^{3} + 2 z^{2} + z + 4, 2 z^{3} + 4 z^{2} + 1, 4 z^{3} + 3 z^{2} + 2 z + 1, 3 z^{3} + 3 z^{2} + 3 z + 2, 3 z^{3} + z + 4, 3 z^{2} + 3 z + 4, 3 z^{3} + 3 z^{2} + 4 z, 3 z^{3} + z^{2} + 4 z + 4, z^{3} + z^{2} + 3 z + 4, z^{3} + 2 z^{2} + 2 z + 3, 2 z^{3} + z^{2} + z + 3, z^{3} + 4 z^{2} + 4 z + 1, 4 z^{3} + 3 z^{2} + 4 z + 3, 3 z^{3} + 2, 2 z^{2} + z + 4, 2 z^{3} + z^{2} + 4 z, z^{3} + 2 z^{2} + z + 1, 2 z^{3} + 4 z + 3, 2 z^{2} + 4 z + 1, 2 z^{3} + 4 z^{2} + z, 4 z^{3} + 4 z^{2} + z + 1, 4 z^{3} + 2 z^{2} + 3 z + 2, 2 z^{3} + 4 z^{2} + 4 z + 2, 4 z^{3} + 2 z^{2} + 3 z + 1, 2 z^{3} + 4 z^{2} + 3 z + 2, 4 z^{3} + z^{2} + 3 z + 1, z^{3} + 4 z^{2} + 3 z + 2, 4 z^{3} + 2 z^{2} + 3, 2 z^{3} + z^{2} + 2, z^{3} + 3 z^{2} + 3 z + 1, 3 z^{3} + 2 z^{2} + 4 z + 3, 2 z^{3} + z^{2} + 2 z + 4, z^{3} + 1, 4 z^{2} + 4 z + 3, 4 z^{3} + 4 z^{2} + 3 z, 4 z^{3} + 4 z^{2} + 2 z + 2, 4 z^{3} + 3 z^{2} + 4 z + 2, 3 z^{3} + 4 z + 2, z^{2} + z + 4, z^{3} + z^{2} + 4 z, z^{3} + 3 z^{2} + 3 z + 3, 3 z^{3} + 2 z^{2} + z + 3, 2 z^{3} + 3 z^{2} + 2 z + 4, 3 z^{3} + 1, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + z + 1, 2 z^{3} + z^{2} + z, z^{3} + 4 z^{2} + z + 1, 4 z^{3} + 4 z + 3, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + z + 1, 3 z^{3} + z^{2} + z, z^{3} + 3 z^{2} + 4 z + 4, 3 z^{3} + 3 z^{2} + 2 z + 3, 3 z^{3} + 4 z^{2} + 2 z + 4, 4 z^{3} + 4 z^{2} + 3 z + 4, 4 z^{3} + 4 z^{2} + z + 2, 4 z^{3} + 2 z^{2} + 4 z + 2, 2 z^{3} + 4 z + 2, 2 z^{2} + 3 z + 1, 2 z^{3} + 3 z^{2} + z, 3 z^{3} + 4 z^{2} + z + 1, 4 z^{3} + 3 z^{2} + 4, 3 z^{3} + z^{2} + z + 2, z^{3} + 3 z^{2} + z + 4, 3 z^{3} + 2 z + 3, 4 z^{2} + 2 z + 4, 4 z^{3} + 2 z^{2} + 4 z, 2 z^{3} + 2 z + 2, 3 z + 1, 3 z^{2} + z, 3 z^{3} + z^{2}, z^{3} + 2 z^{2} + 4 z + 4, 2 z^{3} + 3 z^{2} + 2 z + 3, 3 z^{3} + 4 z + 1, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3 z + 3, 3 z^{3} + 3 z^{2} + 3 z, 3 z^{3} + 4 z + 4, z^{2} + 3 z + 4, z^{3} + 3 z^{2} + 4 z, 3 z^{3} + 3 z^{2} + 3 z + 3, 3 z^{3} + 2 z + 4, 4 z^{2} + 3 z + 4, 4 z^{3} + 3 z^{2} + 4 z, 3 z^{3} + 2 z + 2, 4 z^{2} + z + 4, 4 z^{3} + z^{2} + 4 z, z^{3} + 2 z + 2, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3 z + 3, 2 z^{3} + 3 z^{2} + 3 z, 3 z^{3} + z^{2} + z + 1, z^{3} + 3 z^{2} + 4, 3 z^{3} + 4 z^{2} + 2 z + 3, 4 z^{3} + 4 z^{2} + 2 z + 4, 4 z^{3} + 3 z^{2} + z + 2, 3 z^{3} + 2 z^{2} + 4 z + 2, 2 z^{3} + z^{2} + z + 4, z^{3} + 4 z^{2} + 1, 4 z^{3} + 4 z^{2} + 4 z + 3, 4 z^{3} + 2, z^{2} + 4 z + 2, z^{3} + 4 z^{2} + 2 z, 4 z^{3} + z^{2} + 3 z + 3, z^{3} + 4 z^{2} + 2, 4 z^{3} + 4 z^{2} + 3, 4 z^{3} + z^{2} + 2, z^{3} + z^{2} + 4 z + 2, z^{3} + 3 z^{2} + 3, 3 z^{3} + 4 z^{2} + z + 3, 4 z^{3} + 3 z^{2} + 2 z + 4, 3 z^{3} + 3 z^{2} + z + 2, 3 z^{3} + 3 z^{2} + z + 4, 3 z^{3} + 3 z^{2} + 3 z + 4, 3 z^{3} + 3 z + 4, 3 z + 4, 3 z^{2} + 4 z, 3 z^{3} + 4 z^{2}, 4 z^{3} + 2 z^{2} + 4 z + 4, 2 z^{3} + z + 2, 4 z^{2} + 3 z + 1, 4 z^{3} + 3 z^{2} + z, 3 z^{3} + 2 z^{2} + 2 z + 2, 2 z^{3} + 4 z^{2} + z + 4, 4 z^{3} + 4 z^{2} + 1, 4 z^{3} + z^{2} + 3 z + 2, z^{3} + 4 z^{2} + 4 z + 2, 4 z^{3} + 3 z^{2} + 3, 3 z^{3} + z^{2} + 2, z^{3} + 2 z^{2} + z + 4, 2 z^{3} + 2 z + 3, 4 z + 1, 4 z^{2} + z, 4 z^{3} + z^{2}, z^{3} + z^{2} + 2 z + 2, z^{3} + z^{2} + 3, z^{3} + 4 z^{2} + z + 3, 4 z^{3} + z + 3, 2 z^{2} + 2, 2 z^{3} + 2 z, z + 1, z^{2} + z, z^{3} + z^{2}, z^{3} + 4 z^{2} + 3 z + 3, 4 z^{3} + 2 z^{2} + z + 3, 2 z^{3} + 2 z^{2} + 2, 2 z^{3} + 3 z^{2} + 3 z + 1, 3 z^{3} + z^{2} + 2 z + 1, z^{3} + 4 z^{2} + 4, 4 z^{3} + 4 z^{2} + 2 z + 3, 4 z^{3} + 3 z^{2} + 2, 3 z^{3} + z^{2} + 4 z + 2, z^{3} + z^{2} + z + 4, z^{3} + 2 z + 3, z^{2} + z + 3, z^{3} + z^{2} + 3 z, z^{3} + 2 z^{2} + 3 z + 3, 2 z^{3} + 2 z^{2} + z + 3, 2 z^{3} + 4 z^{2} + 4 z + 1, 4 z^{3} + 2 z^{2} + 2 z + 1, 2 z^{3} + 3 z^{2} + 3 z + 2, 3 z^{3} + z^{2} + 3 z + 1, z^{3} + 4, 4 z^{2} + 2 z + 3, 4 z^{3} + 2 z^{2} + 3 z, 2 z^{3} + 4 z^{2} + 2 z + 2, 4 z^{3} + 3 z + 1, 4 z^{2} + 3 z + 2, 4 z^{3} + 3 z^{2} + 2 z, 3 z^{3} + 3 z^{2} + 2 z + 2, 3 z^{3} + 4 z^{2} + z + 4, 4 z^{3} + 3 z^{2} + 3 z + 4, 3 z^{3} + 4 z^{2} + z + 2, 4 z^{3} + 3 z^{2} + z + 4, 3 z^{3} + 2 z^{2} + z + 2, 2 z^{3} + 3 z^{2} + z + 4, 3 z^{3} + 4 z^{2} + 1, 4 z^{3} + 2 z^{2} + 4, 2 z^{3} + z^{2} + z + 2, z^{3} + 4 z^{2} + 3 z + 1, 4 z^{3} + 2 z^{2} + 4 z + 3, 2 z^{3} + 2, 3 z^{2} + 3 z + 1, 3 z^{3} + 3 z^{2} + z, 3 z^{3} + 3 z^{2} + 4 z + 4, 3 z^{3} + z^{2} + 3 z + 4, z^{3} + 3 z + 4, 2 z^{2} + 2 z + 3, 2 z^{3} + 2 z^{2} + 3 z, 2 z^{3} + z^{2} + z + 1, z^{3} + 4 z^{2} + 2 z + 1, 4 z^{3} + z^{2} + 4 z + 3, z^{3} + 2, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2 z + 2, 4 z^{3} + 2 z^{2} + 2 z, 2 z^{3} + 3 z^{2} + 2 z + 2, 3 z^{3} + 3 z + 1, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2 z + 2, z^{3} + 2 z^{2} + 2 z, 2 z^{3} + z^{2} + 3 z + 3, z^{3} + z^{2} + 4 z + 1, z^{3} + 3 z^{2} + 4 z + 3, 3 z^{3} + 3 z^{2} + z + 3, 3 z^{3} + 3 z^{2} + 2 z + 4, 3 z^{3} + 4 z^{2} + 3 z + 4, 4 z^{3} + 3 z + 4, 4 z^{2} + z + 2, 4 z^{3} + z^{2} + 2 z, z^{3} + 3 z^{2} + 2 z + 2, 3 z^{3} + z^{2} + 3, z^{3} + 2 z^{2} + 2 z + 4, 2 z^{3} + z^{2} + 2 z + 3, z^{3} + 4 z + 1, 3 z^{2} + 4 z + 3, 3 z^{3} + 4 z^{2} + 3 z, 4 z^{3} + 4 z + 4, z + 2, z^{2} + 2 z, z^{3} + 2 z^{2}, 2 z^{3} + 4 z^{2} + 3 z + 3, 4 z^{3} + z^{2} + 4 z + 1, z^{3} + 3 z + 2, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + z + 1, z^{3} + z^{2} + z, z^{3} + 3 z + 3, 2 z^{2} + z + 3, 2 z^{3} + z^{2} + 3 z, z^{3} + z^{2} + z + 1, z^{3} + 4 z + 3, 3 z^{2} + z + 3, 3 z^{3} + z^{2} + 3 z, z^{3} + 4 z + 4, 3 z^{2} + 2 z + 3, 3 z^{3} + 2 z^{2} + 3 z, 2 z^{3} + 4 z + 4, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + z + 1, 4 z^{3} + z^{2} + z, z^{3} + 2 z^{2} + 2 z + 2, 2 z^{3} + z^{2} + 3, z^{3} + 3 z^{2} + 4 z + 1, 3 z^{3} + 3 z^{2} + 4 z + 3, 3 z^{3} + z^{2} + 2 z + 4, z^{3} + 4 z^{2} + 3 z + 4, 4 z^{3} + 2 z^{2} + 2 z + 3, 2 z^{3} + 3 z^{2} + 2, 3 z^{3} + 3 z^{2} + 3 z + 1, 3 z^{3} + 4, 2 z^{2} + 3 z + 4, 2 z^{3} + 3 z^{2} + 4 z, 3 z^{3} + 2 z^{2} + z + 1, 2 z^{3} + 3 z^{2} + 4, 3 z^{3} + 3 z^{2} + 1, 3 z^{3} + 2 z^{2} + 4, 2 z^{3} + 2 z^{2} + 3 z + 4, 2 z^{3} + z^{2} + 1, z^{3} + 3 z^{2} + 2 z + 1, 3 z^{3} + z^{2} + 4 z + 3, z^{3} + z^{2} + 2 z + 4, z^{3} + z^{2} + 2 z + 3, z^{3} + z^{2} + z + 3, z^{3} + z + 3, z + 3, z^{2} + 3 z, z^{3} + 3 z^{2}, 3 z^{3} + 4 z^{2} + 3 z + 3, 4 z^{3} + 2 z + 4, 3 z^{2} + z + 2, 3 z^{3} + z^{2} + 2 z, z^{3} + 4 z^{2} + 4 z + 4, 4 z^{3} + 3 z^{2} + 2 z + 3, 3 z^{3} + 3 z^{2} + 2, 3 z^{3} + 2 z^{2} + z + 4, 2 z^{3} + 3 z^{2} + 3 z + 4, 3 z^{3} + z^{2} + 1, z^{3} + 2 z^{2} + 4, 2 z^{3} + 4 z^{2} + 2 z + 3, 4 z^{3} + 4 z + 1, 3 z + 2, 3 z^{2} + 2 z, 3 z^{3} + 2 z^{2}, 2 z^{3} + 2 z^{2} + 4 z + 4, 2 z^{3} + 2 z^{2} + 1, 2 z^{3} + 3 z^{2} + 2 z + 1, 3 z^{3} + 2 z + 1, 4 z^{2} + 4, 4 z^{3} + 4 z, 2 z + 2, 2 z^{2} + 2 z, 2 z^{3} + 2 z^{2}, 2 z^{3} + 3 z^{2} + z + 1, 3 z^{3} + 4 z^{2} + 2 z + 1, 4 z^{3} + 4 z^{2} + 4, 4 z^{3} + z^{2} + z + 2, z^{3} + 2 z^{2} + 4 z + 2, 2 z^{3} + 3 z^{2} + 3, 3 z^{3} + 3 z^{2} + 4 z + 1, 3 z^{3} + z^{2} + 4, z^{3} + 2 z^{2} + 3 z + 4, 2 z^{3} + 2 z^{2} + 2 z + 3, 2 z^{3} + 4 z + 1, 2 z^{2} + 2 z + 1, 2 z^{3} + 2 z^{2} + z, 2 z^{3} + 4 z^{2} + z + 1, 4 z^{3} + 4 z^{2} + 2 z + 1, 4 z^{3} + 3 z^{2} + 3 z + 2, 3 z^{3} + 4 z^{2} + 4 z + 2, 4 z^{3} + z^{2} + z + 4, z^{3} + 2 z^{2} + z + 2, 2 z^{3} + 3, 3 z^{2} + 4 z + 1, 3 z^{3} + 4 z^{2} + z, 4 z^{3} + 3 z^{2} + 4 z + 4, 3 z^{3} + z + 2, 3 z^{2} + z + 4, 3 z^{3} + z^{2} + 4 z, z^{3} + z^{2} + 4 z + 4, z^{3} + 3 z^{2} + 2 z + 3, 3 z^{3} + z^{2} + z + 3, z^{3} + 3 z^{2} + 2 z + 4, 3 z^{3} + z^{2} + 2 z + 3, z^{3} + 4 z^{2} + 2 z + 4, 4 z^{3} + z^{2} + 2 z + 3, z^{3} + 3 z^{2} + 2, 3 z^{3} + 4 z^{2} + 3, 4 z^{3} + 2 z^{2} + 2 z + 4, 2 z^{3} + 3 z^{2} + z + 2, 3 z^{3} + 4 z^{2} + 3 z + 1, 4 z^{3} + 4, z^{2} + z + 2, z^{3} + z^{2} + 2 z, z^{3} + z^{2} + 3 z + 3, z^{3} + 2 z^{2} + z + 3, 2 z^{3} + z + 3, 4 z^{2} + 4 z + 1, 4 z^{3} + 4 z^{2} + z, 4 z^{3} + 2 z^{2} + 2 z + 2, 2 z^{3} + 3 z^{2} + 4 z + 2, 3 z^{3} + 2 z^{2} + 3 z + 1, 2 z^{3} + 4, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4 z + 4, 3 z^{3} + 4 z^{2} + 4 z, 4 z^{3} + z^{2} + 4 z + 4, z^{3} + z + 2, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4 z + 4, 2 z^{3} + 4 z^{2} + 4 z, 4 z^{3} + 2 z^{2} + z + 1, 2 z^{3} + 2 z^{2} + 3 z + 2, 2 z^{3} + z^{2} + 3 z + 1, z^{3} + z^{2} + 2 z + 1, z^{3} + z^{2} + 4 z + 3, z^{3} + 3 z^{2} + z + 3, 3 z^{3} + z + 3, 3 z^{2} + 2 z + 4, 3 z^{3} + 2 z^{2} + 4 z, 2 z^{3} + z^{2} + 4 z + 4, z^{3} + 2 z^{2} + 1, 2 z^{3} + 4 z^{2} + 4 z + 3, 4 z^{3} + 2 z^{2} + 4 z + 1, 2 z^{3} + 3 z + 2, z^{2} + 3 z + 1, z^{3} + 3 z^{2} + z, 3 z^{3} + 3 z + 3, 2 z + 4, 2 z^{2} + 4 z, 2 z^{3} + 4 z^{2}, 4 z^{3} + 3 z^{2} + z + 1, 3 z^{3} + 2 z^{2} + 3 z + 2, 2 z^{3} + z + 4, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2 z + 2, 2 z^{3} + 2 z^{2} + 2 z, 2 z^{3} + z + 1, 4 z^{2} + 2 z + 1, 4 z^{3} + 2 z^{2} + z, 2 z^{3} + 2 z^{2} + 2 z + 2, 2 z^{3} + 3 z + 1, z^{2} + 2 z + 1, z^{3} + 2 z^{2} + z, 2 z^{3} + 3 z + 3, z^{2} + 4 z + 1, z^{3} + 4 z^{2} + z, 4 z^{3} + 3 z + 3, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2 z + 2, 3 z^{3} + 2 z^{2} + 2 z, 2 z^{3} + 4 z^{2} + 4 z + 4, 4 z^{3} + 2 z^{2} + 1, 2 z^{3} + z^{2} + 3 z + 2, z^{3} + z^{2} + 3 z + 1, z^{3} + 2 z^{2} + 4 z + 3, 2 z^{3} + 3 z^{2} + z + 3, 3 z^{3} + 4 z^{2} + 4 z + 1, 4 z^{3} + z^{2} + 4, z^{3} + z^{2} + z + 2, z^{3} + 3, 4 z^{2} + z + 3, 4 z^{3} + z^{2} + 3 z, z^{3} + 4 z^{2} + 2 z + 2, 4 z^{3} + z^{2} + 3, z^{3} + z^{2} + 2, z^{3} + 4 z^{2} + 3, 4 z^{3} + 4 z^{2} + z + 3, 4 z^{3} + 2 z^{2} + 2, 2 z^{3} + z^{2} + 4 z + 2, z^{3} + 2 z^{2} + 3 z + 1, 2 z^{3} + 2 z^{2} + 4 z + 3, 2 z^{3} + 2 z^{2} + 4 z + 1, 2 z^{3} + 2 z^{2} + 2 z + 1, 2 z^{3} + 2 z + 1, 2 z + 1, 2 z^{2} + z, 2 z^{3} + z^{2}, z^{3} + 3 z^{2} + z + 1, 3 z^{3} + 4 z + 3, z^{2} + 2 z + 4, z^{3} + 2 z^{2} + 4 z, 2 z^{3} + 3 z^{2} + 3 z + 3, 3 z^{3} + z^{2} + 4 z + 1, z^{3} + z^{2} + 4, z^{3} + 4 z^{2} + 2 z + 3, 4 z^{3} + z^{2} + z + 3, z^{3} + 2 z^{2} + 2, 2 z^{3} + 4 z^{2} + 3, 4 z^{3} + 3 z^{2} + 4 z + 1, 3 z^{3} + 3 z + 2, z + 4, z^{2} + 4 z, z^{3} + 4 z^{2}, 4 z^{3} + 4 z^{2} + 3 z + 3, 4 z^{3} + 4 z^{2} + 2, 4 z^{3} + z^{2} + 4 z + 2, z^{3} + 4 z + 2, 3 z^{2} + 3, 3 z^{3} + 3 z, 4 z + 4, 4 z^{2} + 4 z, 4 z^{3} + 4 z^{2}, 4 z^{3} + z^{2} + 2 z + 2, z^{3} + 3 z^{2} + 4 z + 2, 3 z^{3} + 3 z^{2} + 3, 3 z^{3} + 2 z^{2} + 2 z + 4, 2 z^{3} + 4 z^{2} + 3 z + 4, 4 z^{3} + z^{2} + 1, z^{3} + z^{2} + 3 z + 2, z^{3} + 2 z^{2} + 3, 2 z^{3} + 4 z^{2} + z + 3, 4 z^{3} + 4 z^{2} + 4 z + 1, 4 z^{3} + 3 z + 2, 4 z^{2} + 4 z + 2, 4 z^{3} + 4 z^{2} + 2 z, 4 z^{3} + 3 z^{2} + 2 z + 2, 3 z^{3} + 3 z^{2} + 4 z + 2, 3 z^{3} + z^{2} + z + 4, z^{3} + 3 z^{2} + 3 z + 4, 3 z^{3} + 2 z^{2} + 2 z + 3, 2 z^{3} + 4 z^{2} + 2 z + 4, 4 z^{3} + 1, z^{2} + 3 z + 2, z^{3} + 3 z^{2} + 2 z, 3 z^{3} + z^{2} + 3 z + 3, z^{3} + 2 z + 4, z^{2} + 2 z + 3, z^{3} + 2 z^{2} + 3 z, 2 z^{3} + 2 z^{2} + 3 z + 3, 2 z^{3} + z^{2} + 4 z + 1, z^{3} + 2 z^{2} + 2 z + 1, 2 z^{3} + z^{2} + 4 z + 3, z^{3} + 2 z^{2} + 4 z + 1, 2 z^{3} + 3 z^{2} + 4 z + 3, 3 z^{3} + 2 z^{2} + 4 z + 1, 2 z^{3} + z^{2} + 4, z^{3} + 3 z^{2} + 1, 3 z^{3} + 4 z^{2} + 4 z + 3, 4 z^{3} + z^{2} + 2 z + 4, z^{3} + 3 z^{2} + z + 2, 3 z^{3} + 3, 2 z^{2} + 2 z + 4, 2 z^{3} + 2 z^{2} + 4 z, 2 z^{3} + 2 z^{2} + z + 1, 2 z^{3} + 4 z^{2} + 2 z + 1, 4 z^{3} + 2 z + 1, 3 z^{2} + 3 z + 2, 3 z^{3} + 3 z^{2} + 2 z, 3 z^{3} + 4 z^{2} + 4 z + 4, 4 z^{3} + z^{2} + 3 z + 4, z^{3} + 4 z^{2} + z + 2, 4 z^{3} + 3, z^{2} + 2, z^{3} + 2 z, z^{2} + 3 z + 3, z^{3} + 3 z^{2} + 3 z, 3 z^{3} + 2 z^{2} + 3 z + 3, 2 z^{3} + 2 z + 4, 1\right]\)
In [51]:
len(fieldElements)
Out[51]:
624
In [52]:
p^n-1
Out[52]:
624
A non-primitive polynomial won't generate all the nonzero field elements. Note the repetitions in the polynomal list below.¶
In [53]:
f = x^4 + x^2 + 2 ; pretty_print( f )
\(\displaystyle x^{4} + x^{2} + 2\)
In [54]:
isPrimitivePolynomial( f, n, p )
Passed step 1: p=5 >=2 and n = 4 >= 2 Passed step 2: a0 = 2 is a primitive root Passed step 3: f(x) = x^4 + x^2 + 2 has no linear factors Passed step 4: f(x) = x^4 + x^2 + 2 is either irreducible or irreducible ^ power Passed step 5: a = 2 is constant Passed step 6: a = a0 (-1)^n mod p where a0 = 2 Begin step 7: Testing on prime factors p0 ... p2 Skip step 7 test since prime p0 = 2 divides p-1 = 4 Passed step 7 since x^m is not an integer for prime p1 = 3 Failed step 7 since x^m is an integer for prime p2 = 13
Out[54]:
False
In [55]:
fieldElements = generateAllNonzeroFieldElements( f, n, p ); pretty_print( fieldElements )
\(\displaystyle \left[z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1, z, z^{2}, z^{3}, 4 z^{2} + 3, 4 z^{3} + 3 z, 4 z^{2} + 2, 4 z^{3} + 2 z, 3 z^{2} + 2, 3 z^{3} + 2 z, 4 z^{2} + 4, 4 z^{3} + 4 z, 2, 2 z, 2 z^{2}, 2 z^{3}, 3 z^{2} + 1, 3 z^{3} + z, 3 z^{2} + 4, 3 z^{3} + 4 z, z^{2} + 4, z^{3} + 4 z, 3 z^{2} + 3, 3 z^{3} + 3 z, 4, 4 z, 4 z^{2}, 4 z^{3}, z^{2} + 2, z^{3} + 2 z, z^{2} + 3, z^{3} + 3 z, 2 z^{2} + 3, 2 z^{3} + 3 z, z^{2} + 1, z^{3} + z, 3, 3 z, 3 z^{2}, 3 z^{3}, 2 z^{2} + 4, 2 z^{3} + 4 z, 2 z^{2} + 1, 2 z^{3} + z, 4 z^{2} + 1, 4 z^{3} + z, 2 z^{2} + 2, 2 z^{3} + 2 z, 1\right]\)
In [56]:
from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
In [57]:
def findConwayPolynomial( p, n ):
"""Conway polynomials and the related pseudo-Conway polynomials are a type of primitive polynomial with additional nice properties."""
try:
poly = conway_polynomial(p,n)
print( f"Conway polynomial of degree n = {n} modulo p = {p}\n{poly}" )
return poly
except Exception as e:
print( f"Couldn't find a Conway polynomial of degree n = {n} modulo p = {p}: {e}")
return None
def findPseudoConwayPolynomial( p, n ):
"""Conway polynomials and the related pseudo-Conway polynomials are a type of primitive polynomial with additional nice properties."""
PCL = PseudoConwayLattice(p, use_database=False)
try:
poly=PCL.polynomial(n)
print( f"pseudo-Conway polynomial of degree n = {n} modulo p = {p}\n{poly}" )
return poly
except Exception as e:
print( f"Couldn't find a pseudo-Conway polynomial of degree n = {n} modulo p = {p}: {e}")
return None
In [58]:
p = 2 ; n = 600
In [59]:
poly = findConwayPolynomial( p, n )
Couldn't find a Conway polynomial of degree n = 600 modulo p = 2: requested Conway polynomial not in database.
In [60]:
%time poly = findPseudoConwayPolynomial( p, n )
pseudo-Conway polynomial of degree n = 600 modulo p = 2 x^600 + x^599 + x^597 + x^596 + x^591 + x^589 + x^588 + x^587 + x^586 + x^585 + x^584 + x^582 + x^580 + x^578 + x^577 + x^576 + x^575 + x^574 + x^573 + x^571 + x^568 + x^565 + x^564 + x^562 + x^561 + x^558 + x^557 + x^556 + x^555 + x^551 + x^550 + x^549 + x^548 + x^547 + x^546 + x^545 + x^543 + x^542 + x^540 + x^539 + x^534 + x^533 + x^532 + x^525 + x^522 + x^520 + x^518 + x^517 + x^514 + x^513 + x^508 + x^506 + x^505 + x^501 + x^499 + x^497 + x^495 + x^494 + x^486 + x^484 + x^483 + x^479 + x^478 + x^476 + x^475 + x^473 + x^471 + x^470 + x^469 + x^467 + x^466 + x^464 + x^463 + x^462 + x^460 + x^459 + x^458 + x^456 + x^453 + x^452 + x^451 + x^449 + x^448 + x^447 + x^445 + x^444 + x^443 + x^442 + x^441 + x^439 + x^438 + x^437 + x^436 + x^433 + x^432 + x^428 + x^426 + x^425 + x^423 + x^421 + x^420 + x^419 + x^418 + x^416 + x^414 + x^413 + x^410 + x^409 + x^408 + x^406 + x^405 + x^404 + x^403 + x^401 + x^400 + x^398 + x^396 + x^395 + x^392 + x^388 + x^387 + x^386 + x^382 + x^381 + x^380 + x^379 + x^378 + x^376 + x^374 + x^373 + x^368 + x^367 + x^364 + x^358 + x^357 + x^355 + x^348 + x^346 + x^342 + x^341 + x^340 + x^339 + x^338 + x^336 + x^335 + x^333 + x^332 + x^331 + x^330 + x^329 + x^315 + x^314 + x^313 + x^312 + x^309 + x^308 + x^306 + x^305 + x^304 + x^303 + x^302 + x^301 + x^297 + x^295 + x^294 + x^291 + x^289 + x^287 + x^282 + x^281 + x^279 + x^278 + x^274 + x^273 + x^272 + x^266 + x^265 + x^264 + x^258 + x^257 + x^256 + x^255 + x^253 + x^252 + x^251 + x^243 + x^242 + x^240 + x^237 + x^236 + x^235 + x^234 + x^233 + x^232 + x^231 + x^230 + x^229 + x^227 + x^226 + x^225 + x^224 + x^219 + x^218 + x^217 + x^215 + x^211 + x^210 + x^208 + x^204 + x^203 + x^201 + x^199 + x^197 + x^193 + x^189 + x^186 + x^185 + x^182 + x^180 + x^179 + x^176 + x^175 + x^174 + x^169 + x^167 + x^162 + x^159 + x^158 + x^157 + x^156 + x^155 + x^154 + x^150 + x^145 + x^143 + x^139 + x^138 + x^137 + x^132 + x^125 + x^124 + x^122 + x^121 + x^119 + x^116 + x^111 + x^109 + x^107 + x^103 + x^102 + x^100 + x^99 + x^98 + x^94 + x^93 + x^92 + x^91 + x^89 + x^87 + x^86 + x^85 + x^83 + x^82 + x^75 + x^72 + x^69 + x^67 + x^66 + x^59 + x^58 + x^55 + x^52 + x^50 + x^46 + x^44 + x^43 + x^39 + x^38 + x^37 + x^35 + x^31 + x^27 + x^24 + x^23 + x^18 + x^17 + x^9 + x^7 + x^2 + x + 1 CPU times: user 3.93 s, sys: 26.8 ms, total: 3.96 s Wall time: 3.98 s
In [61]:
%time isPrimitivePolynomial( poly, n, p )
Passed step 1: p=2 >=2 and n = 600 >= 2 Passed step 2: a0 = 1 is a primitive root Passed step 3: f(x) = x^600 + x^599 + x^597 + x^596 + x^591 + x^589 + x^588 + x^587 + x^586 + x^585 + x^584 + x^582 + x^580 + x^578 + x^577 + x^576 + x^575 + x^574 + x^573 + x^571 + x^568 + x^565 + x^564 + x^562 + x^561 + x^558 + x^557 + x^556 + x^555 + x^551 + x^550 + x^549 + x^548 + x^547 + x^546 + x^545 + x^543 + x^542 + x^540 + x^539 + x^534 + x^533 + x^532 + x^525 + x^522 + x^520 + x^518 + x^517 + x^514 + x^513 + x^508 + x^506 + x^505 + x^501 + x^499 + x^497 + x^495 + x^494 + x^486 + x^484 + x^483 + x^479 + x^478 + x^476 + x^475 + x^473 + x^471 + x^470 + x^469 + x^467 + x^466 + x^464 + x^463 + x^462 + x^460 + x^459 + x^458 + x^456 + x^453 + x^452 + x^451 + x^449 + x^448 + x^447 + x^445 + x^444 + x^443 + x^442 + x^441 + x^439 + x^438 + x^437 + x^436 + x^433 + x^432 + x^428 + x^426 + x^425 + x^423 + x^421 + x^420 + x^419 + x^418 + x^416 + x^414 + x^413 + x^410 + x^409 + x^408 + x^406 + x^405 + x^404 + x^403 + x^401 + x^400 + x^398 + x^396 + x^395 + x^392 + x^388 + x^387 + x^386 + x^382 + x^381 + x^380 + x^379 + x^378 + x^376 + x^374 + x^373 + x^368 + x^367 + x^364 + x^358 + x^357 + x^355 + x^348 + x^346 + x^342 + x^341 + x^340 + x^339 + x^338 + x^336 + x^335 + x^333 + x^332 + x^331 + x^330 + x^329 + x^315 + x^314 + x^313 + x^312 + x^309 + x^308 + x^306 + x^305 + x^304 + x^303 + x^302 + x^301 + x^297 + x^295 + x^294 + x^291 + x^289 + x^287 + x^282 + x^281 + x^279 + x^278 + x^274 + x^273 + x^272 + x^266 + x^265 + x^264 + x^258 + x^257 + x^256 + x^255 + x^253 + x^252 + x^251 + x^243 + x^242 + x^240 + x^237 + x^236 + x^235 + x^234 + x^233 + x^232 + x^231 + x^230 + x^229 + x^227 + x^226 + x^225 + x^224 + x^219 + x^218 + x^217 + x^215 + x^211 + x^210 + x^208 + x^204 + x^203 + x^201 + x^199 + x^197 + x^193 + x^189 + x^186 + x^185 + x^182 + x^180 + x^179 + x^176 + x^175 + x^174 + x^169 + x^167 + x^162 + x^159 + x^158 + x^157 + x^156 + x^155 + x^154 + x^150 + x^145 + x^143 + x^139 + x^138 + x^137 + x^132 + x^125 + x^124 + x^122 + x^121 + x^119 + x^116 + x^111 + x^109 + x^107 + x^103 + x^102 + x^100 + x^99 + x^98 + x^94 + x^93 + x^92 + x^91 + x^89 + x^87 + x^86 + x^85 + x^83 + x^82 + x^75 + x^72 + x^69 + x^67 + x^66 + x^59 + x^58 + x^55 + x^52 + x^50 + x^46 + x^44 + x^43 + x^39 + x^38 + x^37 + x^35 + x^31 + x^27 + x^24 + x^23 + x^18 + x^17 + x^9 + x^7 + x^2 + x + 1 has no linear factors Passed step 4: f(x) = x^600 + x^599 + x^597 + x^596 + x^591 + x^589 + x^588 + x^587 + x^586 + x^585 + x^584 + x^582 + x^580 + x^578 + x^577 + x^576 + x^575 + x^574 + x^573 + x^571 + x^568 + x^565 + x^564 + x^562 + x^561 + x^558 + x^557 + x^556 + x^555 + x^551 + x^550 + x^549 + x^548 + x^547 + x^546 + x^545 + x^543 + x^542 + x^540 + x^539 + x^534 + x^533 + x^532 + x^525 + x^522 + x^520 + x^518 + x^517 + x^514 + x^513 + x^508 + x^506 + x^505 + x^501 + x^499 + x^497 + x^495 + x^494 + x^486 + x^484 + x^483 + x^479 + x^478 + x^476 + x^475 + x^473 + x^471 + x^470 + x^469 + x^467 + x^466 + x^464 + x^463 + x^462 + x^460 + x^459 + x^458 + x^456 + x^453 + x^452 + x^451 + x^449 + x^448 + x^447 + x^445 + x^444 + x^443 + x^442 + x^441 + x^439 + x^438 + x^437 + x^436 + x^433 + x^432 + x^428 + x^426 + x^425 + x^423 + x^421 + x^420 + x^419 + x^418 + x^416 + x^414 + x^413 + x^410 + x^409 + x^408 + x^406 + x^405 + x^404 + x^403 + x^401 + x^400 + x^398 + x^396 + x^395 + x^392 + x^388 + x^387 + x^386 + x^382 + x^381 + x^380 + x^379 + x^378 + x^376 + x^374 + x^373 + x^368 + x^367 + x^364 + x^358 + x^357 + x^355 + x^348 + x^346 + x^342 + x^341 + x^340 + x^339 + x^338 + x^336 + x^335 + x^333 + x^332 + x^331 + x^330 + x^329 + x^315 + x^314 + x^313 + x^312 + x^309 + x^308 + x^306 + x^305 + x^304 + x^303 + x^302 + x^301 + x^297 + x^295 + x^294 + x^291 + x^289 + x^287 + x^282 + x^281 + x^279 + x^278 + x^274 + x^273 + x^272 + x^266 + x^265 + x^264 + x^258 + x^257 + x^256 + x^255 + x^253 + x^252 + x^251 + x^243 + x^242 + x^240 + x^237 + x^236 + x^235 + x^234 + x^233 + x^232 + x^231 + x^230 + x^229 + x^227 + x^226 + x^225 + x^224 + x^219 + x^218 + x^217 + x^215 + x^211 + x^210 + x^208 + x^204 + x^203 + x^201 + x^199 + x^197 + x^193 + x^189 + x^186 + x^185 + x^182 + x^180 + x^179 + x^176 + x^175 + x^174 + x^169 + x^167 + x^162 + x^159 + x^158 + x^157 + x^156 + x^155 + x^154 + x^150 + x^145 + x^143 + x^139 + x^138 + x^137 + x^132 + x^125 + x^124 + x^122 + x^121 + x^119 + x^116 + x^111 + x^109 + x^107 + x^103 + x^102 + x^100 + x^99 + x^98 + x^94 + x^93 + x^92 + x^91 + x^89 + x^87 + x^86 + x^85 + x^83 + x^82 + x^75 + x^72 + x^69 + x^67 + x^66 + x^59 + x^58 + x^55 + x^52 + x^50 + x^46 + x^44 + x^43 + x^39 + x^38 + x^37 + x^35 + x^31 + x^27 + x^24 + x^23 + x^18 + x^17 + x^9 + x^7 + x^2 + x + 1 is either irreducible or irreducible ^ power Passed step 5: a = 1 is constant Passed step 6: a = a0 (-1)^n mod p where a0 = 1 Begin step 7: Testing on prime factors p0 ... p33 Passed step 7 since x^m is not an integer for prime p0 = 3 Passed step 7 since x^m is not an integer for prime p1 = 5 Passed step 7 since x^m is not an integer for prime p2 = 7 Passed step 7 since x^m is not an integer for prime p3 = 11 Passed step 7 since x^m is not an integer for prime p4 = 13 Passed step 7 since x^m is not an integer for prime p5 = 17 Passed step 7 since x^m is not an integer for prime p6 = 31 Passed step 7 since x^m is not an integer for prime p7 = 41 Passed step 7 since x^m is not an integer for prime p8 = 61 Passed step 7 since x^m is not an integer for prime p9 = 101 Passed step 7 since x^m is not an integer for prime p10 = 151 Passed step 7 since x^m is not an integer for prime p11 = 241 Passed step 7 since x^m is not an integer for prime p12 = 251 Passed step 7 since x^m is not an integer for prime p13 = 331 Passed step 7 since x^m is not an integer for prime p14 = 401 Passed step 7 since x^m is not an integer for prime p15 = 601 Passed step 7 since x^m is not an integer for prime p16 = 1201 Passed step 7 since x^m is not an integer for prime p17 = 1321 Passed step 7 since x^m is not an integer for prime p18 = 1801 Passed step 7 since x^m is not an integer for prime p19 = 4051 Passed step 7 since x^m is not an integer for prime p20 = 8101 Passed step 7 since x^m is not an integer for prime p21 = 61681 Passed step 7 since x^m is not an integer for prime p22 = 63901 Passed step 7 since x^m is not an integer for prime p23 = 100801 Passed step 7 since x^m is not an integer for prime p24 = 268501 Passed step 7 since x^m is not an integer for prime p25 = 340801 Passed step 7 since x^m is not an integer for prime p26 = 2787601 Passed step 7 since x^m is not an integer for prime p27 = 10567201 Passed step 7 since x^m is not an integer for prime p28 = 13334701 Passed step 7 since x^m is not an integer for prime p29 = 1182468601 Passed step 7 since x^m is not an integer for prime p30 = 3173389601 Passed step 7 since x^m is not an integer for prime p31 = 4562284561 Passed step 7 since x^m is not an integer for prime p32 = 1133836730401 Passed step 7 since x^m is not an integer for prime p33 = 1461503031127477825099979369543473122548042956801 CPU times: user 794 ms, sys: 6.44 ms, total: 800 ms Wall time: 806 ms
Out[61]:
True
Try a smaller degree polynomial to see if we can find a Conway polynomial.¶
In [62]:
n = 100
In [63]:
%time poly = findConwayPolynomial( p, n )
Conway polynomial of degree n = 100 modulo p = 2 x^100 + x^57 + x^56 + x^55 + x^52 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^41 + x^37 + x^36 + x^35 + x^34 + x^31 + x^30 + x^27 + x^25 + x^24 + x^22 + x^20 + x^19 + x^16 + x^15 + x^11 + x^9 + x^8 + x^6 + x^5 + x^3 + 1 CPU times: user 287 µs, sys: 10 µs, total: 297 µs Wall time: 295 µs
In [64]:
isPrimitivePolynomial( poly, n, p )
Passed step 1: p=2 >=2 and n = 100 >= 2 Passed step 2: a0 = 1 is a primitive root Passed step 3: f(x) = x^100 + x^57 + x^56 + x^55 + x^52 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^41 + x^37 + x^36 + x^35 + x^34 + x^31 + x^30 + x^27 + x^25 + x^24 + x^22 + x^20 + x^19 + x^16 + x^15 + x^11 + x^9 + x^8 + x^6 + x^5 + x^3 + 1 has no linear factors Passed step 4: f(x) = x^100 + x^57 + x^56 + x^55 + x^52 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^41 + x^37 + x^36 + x^35 + x^34 + x^31 + x^30 + x^27 + x^25 + x^24 + x^22 + x^20 + x^19 + x^16 + x^15 + x^11 + x^9 + x^8 + x^6 + x^5 + x^3 + 1 is either irreducible or irreducible ^ power Passed step 5: a = 1 is constant Passed step 6: a = a0 (-1)^n mod p where a0 = 1 Begin step 7: Testing on prime factors p0 ... p11 Passed step 7 since x^m is not an integer for prime p0 = 3 Passed step 7 since x^m is not an integer for prime p1 = 5 Passed step 7 since x^m is not an integer for prime p2 = 11 Passed step 7 since x^m is not an integer for prime p3 = 31 Passed step 7 since x^m is not an integer for prime p4 = 41 Passed step 7 since x^m is not an integer for prime p5 = 101 Passed step 7 since x^m is not an integer for prime p6 = 251 Passed step 7 since x^m is not an integer for prime p7 = 601 Passed step 7 since x^m is not an integer for prime p8 = 1801 Passed step 7 since x^m is not an integer for prime p9 = 4051 Passed step 7 since x^m is not an integer for prime p10 = 8101 Passed step 7 since x^m is not an integer for prime p11 = 268501
Out[64]:
True