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: |
Description (last modified by )
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
comment:2 Changed 15 months ago by
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
- 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
- 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
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
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
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
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
- 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:10 Changed 14 months ago by
Somewhat related:
comment:11 Changed 13 months ago by
- 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
- Milestone changed from sage-9.4 to sage-9.5
comment:13 Changed 5 months ago by
- Milestone changed from sage-9.5 to sage-9.6
comment:14 Changed 3 weeks ago by
- Milestone changed from sage-9.6 to sage-9.7
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:
To use a random irreducible polynomial as the modulus, specify a variable name.