John Cremona on Tue, 28 Mar 2023 15:16:09 +0200
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: finite fields -- choice of defining polynomial
- To: Pari Users <email@example.com>
- Subject: Re: finite fields -- choice of defining polynomial
- From: John Cremona <firstname.lastname@example.org>
- Date: Tue, 28 Mar 2023 14:14:44 +0100
- Delivery-date: Tue, 28 Mar 2023 15:16:09 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1680009296; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=ic6HHLFyj7eTPJ6xuejauppqSGuVSm+EzeXtrIo+8Lk=; b=MAUvL1bo4yrFYQMXAdYkLm262Vro6kOIPh1U595JigZxq159XYbFkAGzm14q+jxLlQ X0ajBJCgrgVgDtX5yaP/GIJaGF7wAhhXFf/HSIfDGqavE9P6bf4tH3d7frhu3BvU/7D2 kFTJXK9CxNNbnkfYXN8urYDes5Y07kxxA6AdRhYQuBclPPeAkMTjfmQqsiBBcA3qNQee jPYLuUup8v2lsLl5AW7ccKdwMIBj5RPPWCHJuZWZAPnP/xy+8q92UVnaGZR5kxNHWdcV iVWqr7G7QblMZQDUekDT9h4ZaKOz6dGhNRzL62Os+9BJWWG/JOOZfbAAWlYMyavWUtaH NKsg==
- In-reply-to: <ZCLVZ8LKdPM2cPyP@seventeen>
- References: <CAD0p0K4Q0zyO2_L0EfPh0mqwT_vC=ZZ9t1hr=A1W_fx+Nf=FRg@mail.gmail.com> <ZCLVZ8LKdPM2cPyP@seventeen>
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 Tue, Mar 28, 2023 at 10:47:39AM +0000, John Cremona wrote:
> The documentation for ffinit(p,n) does not seem to allow the user to
> specify their own irreducible polynomial (of degree n over Fp). Is that
The only thing ffinit does is to compute an irreducible polynomial.
(I did not choose the name of this function...)
> ffgen(k) does allow k to be an irreducible polynomial rather than the
> output of an ffinit(). If ffgen() is used with a polynomial, can one
> recover the associated ffinit structure, or in some other way do as much
> arithmetic in the field as with an ffinit?
Yes, ffgen does it for you.
> More specifically, has anyone implemented Conway Polynomials in PARI/GP?
Not that I know of.
They are very slow to compute. Magma use precomputed tables to work
around this. If you have such table already, then you can import the polynomial
ffgen has the good property to be fast and deterministic.
For an alternative with similar speed but more functorial property I suggest
<https://arxiv.org/abs/2107.02257> by Franck Lübeck
which is implemented in GAP: