Cryptology ePrint Archive: Report 2014/212
Remarks on the Pocklington and Padr\'o-S\'aez Cube Root Algorithm in $\mathbb F_q$
Geon Heo and Seokhwan Choi and Kwang Ho Lee and Namhun Koo and Soonhak Kwon
Abstract: We clarify and generalize a cube root algorithm in $\mathbb F_q$ proposed by Pocklington, and later rediscovered by Padr\'o and S\'aez. We correct some mistakes in the result of Padr\'o and S\'aez and give a full generalization of their result. We also give the comparison of the implementation of our proposed algorithm with two most popular cube root algorithms, namely the Adleman-Manders-Miller algorithm and the Cipolla-Lehmer algorithm. To the authors' knowledge, our comparison is the first one which compares three fundamental algorithms together.
Category / Keywords: foundations / cube root algorithm, finite field, Pocklington algorithm, Adleman-Manders-Miller algorithm, Cipolla-Lehmer algorithm
Date: received 23 Mar 2014, last revised 25 Mar 2014
Contact author: shkwon at skku edu
Available format(s): PDF | BibTeX Citation
Note: Some minor typos are corrected.
Version: 20140326:042538 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]