Routines for Conway and pseudoConway polynomials.¶
AUTHORS:
 David Roe
 JeanPierre Flori
 Peter Bruin

class
sage.rings.finite_rings.conway_polynomials.
PseudoConwayLattice
(p, use_database=True)¶ Bases:
sage.misc.fast_methods.WithEqualityById
,sage.structure.sage_object.SageObject
A pseudoConway lattice over a given finite prime field.
The Conway polynomial \(f_n\) of degree \(n\) over \(\Bold{F}_p\) is defined by the following four conditions:
 \(f_n\) is irreducible.
 In the quotient field \(\Bold{F}_p[x]/(f_n)\), the element \(x\bmod f_n\) generates the multiplicative group.
 The minimal polynomial of \((x\bmod f_n)^{\frac{p^n1}{p^m1}}\) equals the Conway polynomial \(f_m\), for every divisor \(m\) of \(n\).
 \(f_n\) is lexicographically least among all such polynomials, under a certain ordering.
The final condition is needed only in order to make the Conway polynomial unique. We define a pseudoConway lattice to be any family of polynomials, indexed by the positive integers, satisfying the first three conditions.
INPUT:
p
– prime numberuse_database
– boolean. IfTrue
, use actual Conway polynomials whenever they are available in the database. IfFalse
, always compute pseudoConway polynomials.
EXAMPLES:
sage: from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice sage: PCL = PseudoConwayLattice(2, use_database=False) sage: PCL.polynomial(3) x^3 + x + 1

check_consistency
(n)¶ Check that the pseudoConway polynomials of degree dividing \(n\) in this lattice satisfy the required compatibility conditions.
EXAMPLES:
sage: from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice sage: PCL = PseudoConwayLattice(2, use_database=False) sage: PCL.check_consistency(6) sage: PCL.check_consistency(60) # long time

polynomial
(n)¶ Return the pseudoConway polynomial of degree \(n\) in this lattice.
INPUT:
n
– positive integer
OUTPUT:
 a pseudoConway polynomial of degree \(n\) for the prime \(p\).
ALGORITHM:
Uses an algorithm described in [HL99], modified to find pseudoConway polynomials rather than Conway polynomials. The major difference is that we stop as soon as we find a primitive polynomial.
REFERENCE:
[HL99] L. Heath and N. Loehr (1999). New algorithms for generating Conway polynomials over finite fields. Proceedings of the tenth annual ACMSIAM symposium on discrete algorithms, pp. 429437. EXAMPLES:
sage: from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice sage: PCL = PseudoConwayLattice(2, use_database=False) sage: PCL.polynomial(3) x^3 + x + 1 sage: PCL.polynomial(4) x^4 + x^3 + 1 sage: PCL.polynomial(60) x^60 + x^59 + x^58 + x^55 + x^54 + x^53 + x^52 + x^51 + x^48 + x^46 + x^45 + x^42 + x^41 + x^39 + x^38 + x^37 + x^35 + x^32 + x^31 + x^30 + x^28 + x^24 + x^22 + x^21 + x^18 + x^17 + x^16 + x^15 + x^14 + x^10 + x^8 + x^7 + x^5 + x^3 + x^2 + x + 1

sage.rings.finite_rings.conway_polynomials.
conway_polynomial
(p, n)¶ Return the Conway polynomial of degree \(n\) over
GF(p)
.If the requested polynomial is not known, this function raises a
RuntimeError
exception.INPUT:
p
– prime numbern
– positive integer
OUTPUT:
 the Conway polynomial of degree \(n\) over the finite field
GF(p)
, loaded from a table.
Note
The first time this function is called a table is read from disk, which takes a fraction of a second. Subsequent calls do not require reloading the table.
See also the
ConwayPolynomials()
object, which is the table of Conway polynomials used by this function.EXAMPLES:
sage: conway_polynomial(2,5) x^5 + x^2 + 1 sage: conway_polynomial(101,5) x^5 + 2*x + 99 sage: conway_polynomial(97,101) Traceback (most recent call last): ... RuntimeError: requested Conway polynomial not in database.

sage.rings.finite_rings.conway_polynomials.
exists_conway_polynomial
(p, n)¶ Check whether the Conway polynomial of degree \(n\) over
GF(p)
is known.INPUT:
p
– prime numbern
– positive integer
OUTPUT:
 boolean:
True
if the Conway polynomial of degree \(n\) overGF(p)
is in the database,False
otherwise.
If the Conway polynomial is in the database, it can be obtained using the command
conway_polynomial(p,n)
.EXAMPLES:
sage: exists_conway_polynomial(2,3) True sage: exists_conway_polynomial(2,1) False sage: exists_conway_polynomial(97,200) False sage: exists_conway_polynomial(6,6) False