Opened 15 months ago

Last modified 3 weeks ago

#31434 new defect

Default to random modulus for finite field creation

Reported by: zimmerma Owned by:
Priority: major Milestone: sage-9.7
Component: finite rings Keywords: speed
Cc: slelievre Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #31686 Stopgaps:

Status badges

Description (last modified by slelievre)

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.

Change History (14)

comment:1 Changed 15 months ago by 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

comment:2 Changed 15 months ago by 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.

comment:3 Changed 15 months ago by slelievre

  • Component changed from basic arithmetic to finite rings
  • Description modified (diff)

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.

comment:4 Changed 15 months ago by slelievre

  • Description modified (diff)
  • Keywords speed added
  • Summary changed from GF(p^6) takes ages to Default to random modulus for finite field creation

comment:5 Changed 14 months ago by 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

comment:6 Changed 14 months ago by 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.

comment:7 Changed 14 months ago by 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.

comment:8 Changed 14 months ago by 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).

comment:9 Changed 14 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

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.

comment:11 Changed 13 months ago by slelievre

  • Cc slelievre added
  • Dependencies set to #31686

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

comment:12 Changed 9 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:13 Changed 5 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:14 Changed 3 weeks ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.