GF searches for a dense random modulus outside the Conway range, ignoring FLINT's sparse one

This issue was triaged from bugs/dan/1-galois-fields, one of the 857 files removed from the pre-GitHub bugs/ tree by d2c8d27826 and catalogued in #36. The commentary below was written by Claude (Claude Opus 5, via Claude Code), not by @d-torrance, whose account posted it -- please weigh it accordingly.

Maybe pari's equations for finite fields are better:

Date: Tue, 24 Feb 2009 00:04:33 +0100
To: Pari Developers <pari-dev@list.cr.yp.to>
Subject: Re: ffinit
Mail-Followup-To: Pari Developers <pari-dev@list.cr.yp.to>
In-Reply-To: <158627b90902221108v546a446j6e225581c05cdd1b@mail.gmail.com>
From: Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>

On Sun, Feb 22, 2009 at 07:08:16PM +0000, John Cremona wrote:
> I noticed that ffinit(3,582) produces a polynomial with 333 terms.  I
> would have thought that using a sparse polynomial as the modulus would
> be more efficient (I found x^582 + x^43 + x  - 1, for example).

PARI does not implement a reduction algorithm that is significantly
faster with sparse polynomial:
? P=ffinit(3,582);
? ffgen(P)^(3^582-1);
time = 396 ms.
? Q=(x^582 + x^43 + x - 1)*Mod(1,3);
? ffgen(Q)^(3^582-1);
time = 389 ms.

so the only efficiency considered here is the efficiency of computing the
polynomial itself and there is no contest:

? ffinit(3,582);
time = 12 ms.
? polisirreducible((x^582 + x^43 + x  - 1)*Mod(1,3));
time = 72 ms.
? for(i=2,581,P=x^582+x^i+x-1;if(polisirreducible(P*Mod(1,3)),print(P);break));
x^582 + x^43 + x - 1
time = 2,977 ms.

> I found the course code in polarit3.c which refers to various papers
> and algorithms (Lenstra and Adleman), but can anyone say what are the
> benefits of the polynomials these algorithms produce?  Actually I

1) The algorithm is deterministic so the output is well defined.
2) They have "small" coefficients (when centerlift()'ed).
3) They can be computed very quickly (in polynomial time assuming the
ERH)

> could not quite tell whether in my case it might have been adding a
> random poly of degree < 582 to x^582, in which case the denseness of
> the reslt is not so surprising.

It does not. Actually in this example, it returns the compositum of the
finite fields defined by polsubcyclo(5,2), polsubcyclo(7, 3) and
polsubcyclo(389, 97) (which are all irreducible mod 3).

Cheers,
Bill.

Where it stands today

Unmet — and the answer turns out cheaper than the file imagined, because the sparse modulus it wants is
already available inside M2. Reframed onto FLINT, since PARI left the tree in e79bd82855 (2025-03-07).

What happens today

findGalois (galois.m2:95-121) asks a hook; the only hook is ConwayPolynomials, whose data is
FLINT's Conway table (ConwayPolynomials.m2:13: "the data comes libflint"). Outside that table it
falls to galois.m2:113 — a brute-force search over dense random monic polynomials — and then
findPrimitive.

Measured:

ConwayPolynomials.m2:16 hard-codes false, so GF never sees the sparse path.

GF(3,582) — the PARI thread's own example — does not finish in any practical sense: left running
without a timeout it was still going after 55 minutes at 99% of a core and 261 MB, and was killed
rather than completing.

Two aggravating details

• The modulus is non-deterministic, so GF(3,100) in two sessions gives incompatible fields.
• findPrimitive (galois.m2:118) is computed and then discarded on the FlintBig path
  (galois.m2:174-181) — i.e. the wasted work happens precisely in the slow cases.

Coupled cost for whoever takes it

A non-Conway modulus makes map(GaloisField, GaloisField) error by design
(ConwayPolynomials.m2:42), which is #2143. So switching the fallback changes that behaviour too.

#1917 is adjacent, in the same galois.m2 block.

_{open · disposition issue · source of truth: bug-triage/catalog.tsv}

Start with findGalois in galois.m2:95-121 and the ConwayPolynomials.m2 entries at lines 13, 16, and 42; compare the existing fallback with rawConwayPolynomial(3,100,true). Check GF(3,100) and GF(3,582), including the discarded findPrimitive path in galois.m2:118 and 174-181. Done means the out-of-table path no longer performs the impractical dense random search, with the related field-mapping behavior understood against #2143.