Implemented a "new" algorithm for nth root in finite fields/rings (adapted from the paper "On taking roots in finite fields" by Adelman et al. 1977). My tests show similar or slightly better performance at small prime moduli and significantly better performance in many cases at large prime moduli. This performance increase is mainly due to not relying on K.multiplicative_generator() which needs to factor (p-1) and leads to erratic performance.

Component: finite rings

Author: Hauke Neitzel

Branch/Commit: u/gh-theHawke/finite_field_roots @ 5845925

Issue created by migration from https://trac.sagemath.org/ticket/28585