Opened 9 years ago
Last modified 7 years ago
#14551 new enhancement
Tuning nth root for finite fields
Reported by: | roed | Owned by: | cpernet |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | finite rings | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
As of #7931, Sage uses an algorithm due to Johnston for computing the n
th root of finite field elements and elements modulo n
. In GF(p)
for very large p
and small n
this algorithm is inferior to just factoring x^n-a
, since it requires a primitive root modulo p
. Preliminary timings indicate that Johnston's algorithm is sometimes faster even in the range of 80
decimal digits, but it sometimes fails spectacularly with runtime 300 times slower than factoring the polynomial.
We should add the polynomial option as an algorithm to n
th root and have a reasonable default based on the size of n
and p
.
Change History (5)
comment:1 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:2 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:3 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:4 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:5 Changed 7 years ago by
- Component changed from basic arithmetic to finite rings
- Owner changed from AlexGhitza to cpernet