id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
14551,Tuning nth root for finite fields,roed,cpernet,"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`.",enhancement,new,major,sage-6.4,finite rings,,,,,,,N/A,,,,,