You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
As of #7931, Sage uses an algorithm due to Johnston for computing the
n
th root of finite field elements and elements modulon
. InGF(p)
for very largep
and smalln
this algorithm is inferior to just factoringx^n-a
, since it requires a primitive root modulop
. Preliminary timings indicate that Johnston's algorithm is sometimes faster even in the range of80
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 ofn
andp
.Component: finite rings
Issue created by migration from https://trac.sagemath.org/ticket/14551
The text was updated successfully, but these errors were encountered: