0
$\begingroup$

Is there a site that has tables of irreducible polynomials over Finite prime fields? Preferably up to at least degree 10 for primes 2, 3, and 5.

Also, what programming language is helpful in factoring polynomials over finite fields?

$\endgroup$
2
$\begingroup$

Tables are not so good to work with, one has to copy+paste. A mathematically good way to use computer algebra support for this task is sage. Here are some code snippets that answer the one or the other related aspect.

sage: F = GF(5)
sage: R.<x> = PolynomialRing(F)
sage: F
Finite Field of size 5
sage: R
Univariate Polynomial Ring in x over Finite Field of size 5
sage: R.irreducible_element?
sage: R.irreducible_element(12)
x^12 + x^7 + x^6 + 4*x^4 + 4*x^3 + 3*x^2 + 2*x + 2
sage: # The above is a possible choice of an irreductible polynomial.
sage: minimal_polynomials = list( set( [ f.minpoly() for f in GF(5**6) ] ) )
sage: minimal_polynomials = [ p for p in minimal_polynomials if p.degree() == 6 ] 
sage: minimal_polynomials . sort()
sage: len( minimal_polynomials )
2580
sage: for p in minimal_polynomials[:10]:
....:     print p
....:     
x^6 + x + 2
x^6 + 2*x + 3
x^6 + 3*x + 3
x^6 + 4*x + 2
x^6 + x^2 + x + 1
x^6 + x^2 + x + 3
x^6 + x^2 + 2*x + 2
x^6 + x^2 + 2*x + 4
x^6 + x^2 + 3*x + 2
x^6 + x^2 + 3*x + 4
sage: # These are the first ten minimal polynomials of some elements in GF(5**6), after sorting them

sage: # Alternatively, we can factor the polynomial extracted from the Frobenius isomorphism
sage: F = GF(2)
sage: K.<a> = GF(2**9)
sage: R.<x> = PolynomialRing(F)
sage: myfactors = [ f for f, multiplicity in (x^(2^9)-x).factor() if f.degree() == 9 ]
sage: len(myfactors)
56
sage: myfactors.sort()
sage: for f in myfactors[:10]:
....:     print f
....:     
x^9 + x + 1
x^9 + x^4 + 1
x^9 + x^4 + x^2 + x + 1
x^9 + x^4 + x^3 + x + 1
x^9 + x^5 + 1
x^9 + x^5 + x^3 + x^2 + 1
x^9 + x^5 + x^4 + x + 1
x^9 + x^6 + x^3 + x + 1
x^9 + x^6 + x^4 + x^3 + 1
x^9 + x^6 + x^4 + x^3 + x^2 + x + 1

The code is "python-like", object-oriented, and the user has an easy game in the i(ron)python console. For instance, for a given instance of some object, using the dot-method, and hitting the TAB, one gets a list of all possible methods. For each method, putting a question mark after it, one gets the help (with examples). The community is active and open, open code makes this possible: asksage

$\endgroup$
  • $\begingroup$ Looks solid. I'll give it a peek. Thank you! $\endgroup$ – Sean Nemetz Jul 5 '18 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.