Routines for Conway and pseudo-Conway polynomials

AUTHORS:

• David Roe

• Jean-Pierre Flori

• Peter Bruin

class sage.rings.finite_rings.conway_polynomials.PseudoConwayLattice(p, use_database=True)

Bases: WithEqualityById, SageObject

A pseudo-Conway lattice over a given finite prime field.

The Conway polynomial $f_n$ of degree $n$ over ${\mathbf{F}}_p$ is defined by the following four conditions:

• $f_n$ is irreducible.

• In the quotient field ${\mathbf{F}}_p[x]/(f_n)$, the element $xmod{f}_n$ generates the multiplicative group.

• The minimal polynomial of $(xmod{f}_n{)}^{\frac{p^n-1}{p^m-1}}$ 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 pseudo-Conway lattice to be any family of polynomials, indexed by the positive integers, satisfying the first three conditions.

INPUT:

• p – prime number

• use_database – boolean. If True, use actual Conway polynomials whenever they are available in the database. If False, always compute pseudo-Conway polynomials.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
sage: PCL = PseudoConwayLattice(2, use_database=False)
sage: PCL.polynomial(3)   # random
x^3 + x + 1

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
>>> PCL = PseudoConwayLattice(Integer(2), use_database=False)
>>> PCL.polynomial(Integer(3))   # random
x^3 + x + 1

Sage Live

# needs sage.rings.finite_rings
from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
PCL = PseudoConwayLattice(2, use_database=False)
PCL.polynomial(3)   # random

check_consistency(n)

Check that the pseudo-Conway polynomials of degree dividing $n$ in this lattice satisfy the required compatibility conditions.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
>>> PCL = PseudoConwayLattice(Integer(2), use_database=False)
>>> PCL.check_consistency(Integer(6))
>>> PCL.check_consistency(Integer(60))  # long time

Sage Live

# needs sage.rings.finite_rings
from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
PCL = PseudoConwayLattice(2, use_database=False)
PCL.check_consistency(6)
PCL.check_consistency(60)  # long time

polynomial(n)

Return the pseudo-Conway polynomial of degree $n$ in this lattice.

INPUT:

• n – positive integer

OUTPUT: a pseudo-Conway polynomial of degree $n$ for the prime $p$

ALGORITHM:

Uses an algorithm described in [HL1999], modified to find pseudo-Conway polynomials rather than Conway polynomials. The major difference is that we stop as soon as we find a primitive polynomial.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
sage: PCL = PseudoConwayLattice(2, use_database=False)
sage: PCL.polynomial(3)   # random
x^3 + x + 1
sage: PCL.polynomial(4)   # random
x^4 + x^3 + 1
sage: PCL.polynomial(60)  # random
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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
>>> PCL = PseudoConwayLattice(Integer(2), use_database=False)
>>> PCL.polynomial(Integer(3))   # random
x^3 + x + 1
>>> PCL.polynomial(Integer(4))   # random
x^4 + x^3 + 1
>>> PCL.polynomial(Integer(60))  # random
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 Live

# needs sage.rings.finite_rings
from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
PCL = PseudoConwayLattice(2, use_database=False)
PCL.polynomial(3)   # random
PCL.polynomial(4)   # random
PCL.polynomial(60)  # random

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 number

• n – 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

sage: conway_polynomial(2,5)                                                    # needs conway_polynomials
x^5 + x^2 + 1
sage: conway_polynomial(101,5)                                                  # needs conway_polynomials
x^5 + 2*x + 99
sage: conway_polynomial(97,101)                                                 # needs conway_polynomials
Traceback (most recent call last):
...
RuntimeError: requested Conway polynomial not in database.

Python

>>> from sage.all import *
>>> conway_polynomial(Integer(2),Integer(5))                                                    # needs conway_polynomials
x^5 + x^2 + 1
>>> conway_polynomial(Integer(101),Integer(5))                                                  # needs conway_polynomials
x^5 + 2*x + 99
>>> conway_polynomial(Integer(97),Integer(101))                                                 # needs conway_polynomials
Traceback (most recent call last):
...
RuntimeError: requested Conway polynomial not in database.

Sage Live

conway_polynomial(2,5)                                                    # needs conway_polynomials
conway_polynomial(101,5)                                                  # needs conway_polynomials
conway_polynomial(97,101)                                                 # needs conway_polynomials

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 number

• n – positive integer

OUTPUT:

• boolean: True if the Conway polynomial of degree $n$ over GF(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

sage: exists_conway_polynomial(2,3)                                             # needs conway_polynomials
True
sage: exists_conway_polynomial(2,-1)
False
sage: exists_conway_polynomial(97,200)
False
sage: exists_conway_polynomial(6,6)
False

Python

>>> from sage.all import *
>>> exists_conway_polynomial(Integer(2),Integer(3))                                             # needs conway_polynomials
True
>>> exists_conway_polynomial(Integer(2),-Integer(1))
False
>>> exists_conway_polynomial(Integer(97),Integer(200))
False
>>> exists_conway_polynomial(Integer(6),Integer(6))
False

Sage Live

exists_conway_polynomial(2,3)                                             # needs conway_polynomials
exists_conway_polynomial(2,-1)
exists_conway_polynomial(97,200)
exists_conway_polynomial(6,6)

Make live