有限域上方程 x^r=a 的求解

Taking roots over finite field is widely exploited in the domains including public key cryptosystem, the quadratic sieve factoring algorithm, the order calculation and primality testing on elliptic curve. In this paper, we propose a new efficient randomized algorithm to take cubic roots over F_p, i.e, x³ = a, and we give the expected running time with the help of cyclotomy theory. Our main idea comes from Berlekamp's square root method over F_p. Unlike previous work, we use quadratic residue and non-residue to compute cubic root, and cubic non-residue is not involved in the procedure. The expected running time is O (log² p (log log p)) bit operations. Then, we extend this method to arbitrary cubic equation, e.g. x³ + ax² + bx + c = 0. We calculate the solution number of x³ + ax² + bx + c = 0 and also give all the solutions. Besides, we extend the Cipolla-Lehmer algorithm to compute the root of x^r = a where r is a prime power, by taking the norm of element in finite field. By constructing monic irreducible polynomial f ( x) over F_q [x], we exhibit our algorithm to calculate solution to the equation x^r = a, deg ( f) = r and f ( x) with constant term (-1)^r a. Then, combining Davenport-Hasse relation and Double Counting, we get the expecting running time O(log q) operations in F_q. For all the prime power r s.t. r⁴ ≤ q, our algorithm is practical.