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:

Status badges


As of #7931, Sage uses an algorithm due to Johnston for computing the nth 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 nth root and have a reasonable default based on the size of n and p.

Change History (5)

comment:1 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:5 Changed 7 years ago by jdemeyer

  • Component changed from basic arithmetic to finite rings
  • Owner changed from AlexGhitza to cpernet
Note: See TracTickets for help on using tickets.