Default to random modulus for finite field creation

[zimmermann6]

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.

Depends on #31686

CC: @slel

Component: finite rings

Keywords: speed

Issue created by migration from https://trac.sagemath.org/ticket/31434

[slel]

comment:1

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

[JohnCremona]

comment:2

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.

[slel]

Description changed:

--- 
+++ 
@@ -1,11 +1,17 @@
-this was reported to me by my colleague Pierrick Gaudry:
+Reported to Paul Zimmermann by his colleague Pierrick Gaudry.
+
+Observed with [SageMath](../wiki/SageMath) version 9.0 based on Python 3.7.3.

-┌────────────────────────────────────────────────────────────────────┐ -│ SageMath version 9.0, Release Date: 2020-01-01 │ -│ Using Python 3.7.3. Type "help()" for help. │ -└────────────────────────────────────────────────────────────────────┘ sage: p = 135066410865995223349603927 sage: Fp6 = GF(p^6)

 After two minutes, it did not finish...
+
+The field is created almost instantly
+if a generator name is specified:
+
+```
+sage: Fp6 = GF(p^6, 'a')
+```
+

[slel]

comment:3

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.

[slel]

Description changed:

--- 
+++ 
@@ -1,6 +1,6 @@
 Reported to Paul Zimmermann by his colleague Pierrick Gaudry.

-Observed with [SageMath](../wiki/SageMath) version 9.0 based on Python 3.7.3.
+In [SageMath](../wiki/SageMath) version 9.0 (but also 9.2) this takes ages:

sage: p = 135066410865995223349603927 @@ -8,10 +8,14 @@

 After two minutes, it did not finish...

-The field is created almost instantly
-if a generator name is specified:
+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.

[slel]

Changed keywords from none to speed

[roed314]

comment:5

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

[zimmermann6]

comment:6

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.

[roed314]

comment:7

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.

[zimmermann6]

comment:8

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]

comment:9

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.

[slel]

comment:10

Somewhat related:

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

[slel]

comment:11

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

[slel]

Dependencies: #31686

[fredrik-johansson]

See also this example reported on reddit: https://old.reddit.com/r/math/comments/1e5115x/in_sagemath_how_to_use_gf_on_a_very_large_finite/

[ytrezq]

@fredrik-johansson : yep. The alternatives mentioned don’t work if you want the results of a scalar point multiplication on a curve.

[ytrezq]

@zimmermann6 : j’ai lu votre livre. Du coup comment faire un Point_sur_une_courbe.E_extend(nouvelle_courbe) sans utiliser SageMath ?

More generally would it be possible to make computing the pseudo‑conway polynomial non blocking : I’m meaning computing them in a separate thread and making the thread blocking only if it’s required to access them (because I suppose accessing them isn’t required for declaring a binary curve).

[zimmermann6]

@ytrezq please write in english. What you suggest does not solve the issue of this ticket, since if the seperate thread does not finish, you have a problem.

[ytrezq]

@zimmermann6 what I m meaning is it s normally not needed to get the underlying prime in order to declare a binary curve.

Though Ok. I debugged the issue. Even when using (prime,power) as GF parameters, Sage is is using days in ifactor.c in ellfacteur. So not building pseudo conway polynomials.

Why it doesn t use the faster code that checks for prime power?

[ytrezq]

@slel Isn t there a way to specify the prime and power used to build the finite field directly which would avoid factoring a number several time larger than the best factorizarion record?