New cube root algorithm based on third order linear recurrence relation in finite field, preprint, available from http://eprint.iacr

We present a new cube root algorithm in finite field Fq with q a power of prime, which extends Cipolla-Lehmer type algorithms and has lower complexity than Tonelli-Shanks type algorithms. Efficient computation of r-th root in Fq has many applications in computational number theory and many other related areas. There are two standard algorithms for computing r-th root in finite field. One is Adleman-Manders-Miller algorithm which is a straightforward generalization of Tonelli-Shanks square root algorithm. Another algorithm is a also a natural generalization of Cipolla-Lehmer square root algorithm. Original Cipolla-Lehmer algorithm requires one to use extension field arithmetic in Fq2, but one can use second order linear recurrence relation without any extension field arithmetic. Moreover a special type of Lucas sequence method of Müller gives a new square root algorithm which is consistently better than Tonelli-Shanks. However unlike the cases of Tonell-Shanks and Cipolla-Lehmer, extending the idea of Müller to cube root algorithm is not so obvious because, for given cubic residue c 2 Fq