Re: finite fields -- choice of defining polynomial

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Tue, Mar 28, 2023 at 02:14:44PM +0100, John Cremona wrote:
> Thanks, Bill.
> 
> The reason we want to use Conway polynomials is that they are primitive
> (the root generates the multiplicative group), and also, crucially, that
> these roots form a coherent system of all roots of unity of prime-to-ell
> order in the algebraic closure of F_ell.
> 
> I do know that there is no known way to compute them, so that using
> precomputed lists (for some small values of ell and d) is desirable.  But I
> bet that a list of all known Conway polynomials would take up less space as
> an optional package than my database of ellipticcurves of conductor up to
> 500000! ( I did not check this reckless claim...)
> 
> Still, I am glad that ffinit() is deterministic so will not change.

On the other hand, unfortunately ffprimroot is randomized, so the following
minpoly(ffprimroot(ffgen([p,n]))) (which returns a primitive polynomial)
is not deterministic.

However computing primitive polynomials is much more expensive than ffinit
since it requires to factor p^n-1. (Magma also have tables of such factorizations).

Cheers,
Bill.