Default to random modulus for finite field creation

[zimmerma]

Reported to Paul Zimmermann by his colleague Pierrick Gaudry.

In SageMath version 9.0 (but also 9.2) this takes ages:

sage: p = 135066410865995223349603927
sage: Fp6 = GF(p^6)

After two minutes, it did not finish...

By contrast, if a generator name is specified, the field is created almost instantly:

sage: Fp6 = GF(p^6, 'a')

This goes back to #17569 where specifying a generator name was made optional, and where the default, when no generator name is given, was set to using a pseudo-Conway modulus.

[slelievre]

If no variable name is provided, Sage tries to compute a pseudo-Conway polynomial to use as the modulus.

The ​finite field constructor documentation warns:

Note that the computation of pseudo-Conway polynomials is expensive when the degree is large and highly composite. If a variable name is specified then a random polynomial is used instead, which will be much faster to find.

To use a random irreducible polynomial as the modulus, specify a variable name.

sage: p = 135066410865995223349603927
sage: timeit("F = GF(p^6, 'a')")
5 loops, best of 3: 35.6 ms per loop

[cremona]

It seems rather obscure to me to behave this way. Does someone have a reason? I think that a user would assume that if not giving a variable name is allowed (unlike in a NumberField? constructor, for example), the system would just choose some default name, not that this would trigger potentiall large computation. I think that should only be done if some explicit parameter is set to ask it to.

[slelievre]

I think this is from #17569 (Allow creating finite fields without a variable name).

I would tend to agree that a faster default would better serve the casual user.

Let advanced users add keyword arguments for specific time-consuming behaviours.

[roed]

I think a change for very large primes is wise, but I think it's convenient that the following works, which would fail if we made the change suggested here:

sage: k = GF(4)
sage: l = GF(8)
sage: x = k.gen() + l.gen(); x
z6^5 + z6^4 + z6^3 + z6 + 1
sage: x.parent()
Finite Field in z6 of size 2^6

Here are some alternative suggestions to just always using random polynomials

• Use a cutoff depending on p: current behavior below the cutoff and random polynomial above the cutoff
• Print a warning (with an explanation of how to get different behavior) whenever an expensive computation is going to start

[zimmerma]

the first suggestion (using a cutoff) sounds good to me. For GF(p^6) and p having less than 50 bits the initialization takes less than one second.

[roed]

I think I would go with a slightly smaller threshold, since I want it to depend only on p and not on the degree.

sage: p = previous_prime(2^16-456)                                                                                                                                                                                                                 
sage: %time K = GF(p^6)                                                                                                                                                                                                                            
CPU times: user 14.1 ms, sys: 891 µs, total: 15 ms
Wall time: 14.2 ms
sage: p = previous_prime(2^32-34567)                                                                                                                                                                                                               
sage: %time K = GF(p^6)                                                                                                                                                                                                                            
CPU times: user 43.1 ms, sys: 12.7 ms, total: 55.8 ms
Wall time: 55.7 ms

Note that the time increases for highly composite degree

sage: p = previous_prime(2^16-456)                                                                                                                                                                                                                 
sage: %time K = GF(p^24)                                                                                                                                                                                                                           
CPU times: user 214 ms, sys: 27.5 ms, total: 241 ms
Wall time: 252 ms

And sometimes you just hit integers that are hard to factor

sage: factor(p^23 - 1)
...

I have some sympathy with John Cremona's objection that depending the presence or absence of a generator name is strange. I think there's just value in having both mechanisms be easy to construct, and having natural coercions available.

[zimmerma]

if it is related to the difficulty of factoring p^k-1 then the threshold should be on the number of bits of p^k (to be adjusted for small p if the Cunningham tables are used).

[mkoeppe]

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

[slelievre]

Somewhat related:

• ​Ask Sage question 56357: Large finite fields with modulus='primitive' do not satisfy equality

[slelievre]

The main blocking step turns out to be factoring p^n - 1. Luckily #31686 helps a lot:

sage: p = 135066410865995223349603927
sage: %time F = GF(p^6, 'a')
CPU times: user 93.6 ms, sys: 1.8 ms, total: 95.4 ms
Wall time: 174 ms
sage: %time F = GF(p^6)
CPU times: user 1.48 s, sys: 7.48 ms, total: 1.49 s
Wall time: 1.91 s