def numPolynomials(p,n):
    """"The total number of polynomials of degree n modulo p."""
    return p ^ n

def numPrimitivePolynomials(p,n):
    """"The number of primitive polynomials of degree n modulo p."""
    return euler_phi( p ^ n - 1 ) / n

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 )

p = 5 ; n = 4

numPolynomials(p,n)

625

numPrimitivePolynomials(p,n)

48

N(probabilityRandomPolynomialIsPrimitive(p,n),digits=3)

0.0768

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

isPrimRoot(3,p)

True

[Mod(3^i,p) for i in range(1,p)]

[3, 4, 2, 1]

[Mod(4^i,p) for i in range(1,p)]

[4, 1, 4, 1]

Mod(4,p).multiplicative_order()

2

R.<x>=PolynomialRing(GF(p))

R

Univariate Polynomial Ring in x over Finite Field of size 5

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)

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)

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

f = x^4 + x^2 + 2*x + 3 ; pretty_print(f)

numPolynomialsWithLinearFactors(p,n)

420

N(probRandomPolyHasLinearFactors(p,n),digits=3)

0.672

polynomialHasLinearFactor(f)

False

[f(k) for k in range(0,p)]

[3, 2, 2, 4, 3]

polynomialHasLinearFactor((x-2)*(x-3))

True

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

help(isConstantPolynomial)

Help on function isConstantPolynomial in module __main__:

isConstantPolynomial(f)
    Is the polynomial constant?

isConstantPolynomial( f )

False

isConstantPolynomial(3)

True

Q.<z>=R.quotient( f )

Q

Univariate Quotient Polynomial Ring in z over Finite Field of size 5 with modulus x^4 + x^2 + 2*x + 3

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)]

listOfPowers = powersOfXModfp(f,n,p) ; pretty_print( listOfPowers )

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)

m = generateQIMatrix(f,n,p) ; pretty_print( m )

k = kernel(m) ; k

Vector space of degree 4 and dimension 1 over Finite Field of size 5
Basis matrix:
[1 0 0 0]

m.left_nullity()

1

def hasTwoOrMoreDistinctIrreducibleFactors(f,n,p):
    m=generateQIMatrix(f,n,p)
    return m.left_nullity() >= 2

hasTwoOrMoreDistinctIrreducibleFactors(f,n,p)

False

r=(p^n-1)//(p-1) ; r

156

factorization = factor(r) ; pretty_print( factorization )

# p = 2 ; n = 929 ; r=(p^n-1)//(p-1) ; pretty_print( r )
# factorization = factor(r) ; pretty_print( factorization )

type( 156 / 4 )

<class 'sage.rings.rational.Rational'>

type( 156 // 4 )

<class 'sage.rings.integer.Integer'>

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

distinctPrimeFactors(r)

[2, 3, 13]

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

p = 5 ; n = 4

f = x^4 + x^2 + 2*x + 2 ; pretty_print( f )

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

True

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

fieldElements = generateAllNonzeroFieldElements( f, n, p ) ; pretty_print( fieldElements )

len(fieldElements)

624

p^n-1

624

f = x^4 + x^2 + 2 ; pretty_print( f )

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

False

fieldElements = generateAllNonzeroFieldElements( f, n, p ); pretty_print( fieldElements )

from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice

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

p = 2 ; n = 600

poly = findConwayPolynomial( p, n )

Couldn't find a Conway polynomial of degree n = 600 modulo p = 2:  requested Conway polynomial not in database.

p = 2 ; n = 199

%time poly = findConwayPolynomial( p, n )

Conway polynomial of degree n = 199 modulo p = 2
x^199 + x^7 + x^6 + x^5 + x^3 + x^2 + 1
CPU times: user 565 μs, sys: 63 μs, total: 628 μs
Wall time: 595 μs

isPrimitivePolynomial( poly, n, p )

Passed step 1:  p=2 >=2 and n = 199 >= 2
Passed step 2:  a0 = 1 is a primitive root
Passed step 3:  f(x) = x^199 + x^7 + x^6 + x^5 + x^3 + x^2 + 1 has no linear factors
Passed step 4:  f(x) = x^199 + x^7 + x^6 + x^5 + x^3 + x^2 + 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 ... p1
  Passed step 7 since x^m is not an integer for prime p0 =                                     164504919713
  Passed step 7 since x^m is not an integer for prime p1 =                                     4884164093883941177660049098586324302977543600799

True

Finding Primitive Polynomials¶

This notebook is called `PrimpolySageMath.ipynb`¶

Counting the number of primitive polynomials of degree $n$ modulo $p$. The probability that a polynomial chosen at random is primitive.¶

Let's do a low degree example with a small modulus.¶

Testing whether $a$ is a primitive root of $p$¶

Since 3 is a primitive root of 5, it generates the nonzero elements of GF(5).¶

But 4 is not a primitive root of 5 since its order is only 2 instead of 4.¶

Define the ring of polynomials with coefficients over $GF(p)$ with generator $x$.¶

Testing if polynomials have linear factors.¶

An example polynomial of low degree.¶

Confirm that f has no linear factors.¶

Confirm that this polynomial with two roots, i.e. two linear factors, does indeed pass the one or more linear factors test.¶

Testing if a polynomial is constant¶

Define the quotient ring $Q$ of polynomials modulo $f(x)$ with generator $z$.¶

We previously defined the variable x to denote the generator for the polynomial ring R with coefficients in $GF(p)$. Sage is smart enough to remember that. So let's change the name from 'x' to 'z' instead.¶

Compute the powers $z^n (mod f(x), p)$¶

Irreducibility Testing¶

Compute $\mathbf{Q-I}$ where the $n$ rows of matrix $\mathbf{Q}$ are the coefficients of the powers $z^0, z^p, ..., z^{np} (mod f(x), p)$¶

This is the left kernel (nullspace), i.e. all vectors w satisfying $\mathbf{w A = 0}$¶

Factor the expression r into distinct primes.¶

NOTE: Use // for integer divide instead of / or else we'll get a rational number type for the answer even if $(p-1) | (p^n-1)$.¶

Distinct prime factors of r¶

Testing whether a polynomial $f(x)$ modulo $p$ is primitive.¶

Examples: Primitive and non-primitive polynomials as generators of field elements.¶

A primitive polynomial generates all of the $p^n - 1$ nonzero field elements.¶

A non-primitive polynomial won't generate all the nonzero field elements. Note the repetitions in the polynomal list below.¶

Finding Conway polynomials.¶

Find a Conway polynomial and test it for primitivity.¶

Finding Primitive Polynomials¶

This notebook is called PrimpolySageMath.ipynb¶

Counting the number of primitive polynomials of degree $n$ modulo $p$. The probability that a polynomial chosen at random is primitive.¶

Let's do a low degree example with a small modulus.¶

Testing whether $a$ is a primitive root of $p$¶

Since 3 is a primitive root of 5, it generates the nonzero elements of GF(5).¶

But 4 is not a primitive root of 5 since its order is only 2 instead of 4.¶

Define the ring of polynomials with coefficients over $GF(p)$ with generator $x$.¶

Testing if polynomials have linear factors.¶

An example polynomial of low degree.¶

Confirm that f has no linear factors.¶

Confirm that this polynomial with two roots, i.e. two linear factors, does indeed pass the one or more linear factors test.¶

Testing if a polynomial is constant¶

Define the quotient ring $Q$ of polynomials modulo $f(x)$ with generator $z$.¶

We previously defined the variable x to denote the generator for the polynomial ring R with coefficients in $GF(p)$. Sage is smart enough to remember that. So let's change the name from 'x' to 'z' instead.¶

Compute the powers $z^n (mod f(x), p)$¶

Irreducibility Testing¶

Compute $\mathbf{Q-I}$ where the $n$ rows of matrix $\mathbf{Q}$ are the coefficients of the powers $z^0, z^p, ..., z^{np} (mod f(x), p)$¶

This is the left kernel (nullspace), i.e. all vectors w satisfying $\mathbf{w A = 0}$¶

Factor the expression r into distinct primes.¶

NOTE: Use // for integer divide instead of / or else we'll get a rational number type for the answer even if $(p-1) | (p^n-1)$.¶

Distinct prime factors of r¶

Testing whether a polynomial $f(x)$ modulo $p$ is primitive.¶

Examples: Primitive and non-primitive polynomials as generators of field elements.¶

A primitive polynomial generates all of the $p^n - 1$ nonzero field elements.¶

A non-primitive polynomial won't generate all the nonzero field elements. Note the repetitions in the polynomal list below.¶

Finding Conway polynomials.¶

Conway polynomials and the related pseudo-Conway polynomials are a type of primitive polynomial with additional nice properties.¶

Find a Conway polynomial and test it for primitivity.¶

This notebook is called `PrimpolySageMath.ipynb`¶