Remarks on the Pocklington and Padró-Sáez Cube Root Algorithm in $\mathbb F_q$

Geon Heo; Seokhwan Choi; Kwang Ho Lee; Namhun Koo; Soonhak Kwon

Paper 2014/212

Remarks on the Pocklington and Padró-Sáez Cube Root Algorithm in $\mathbb F_q$

Geon Heo, Seokhwan Choi, Kwang Ho Lee, 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ó and Sáez. We correct some mistakes in the result of Padró and Sáez 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.

Note: Some minor typos are corrected.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: cube root algorithm finite field Pocklington algorithm Adleman-Manders-Miller algorithm Cipolla-Lehmer algorithm
Contact author(s): shkwon @ skku edu
History: 2014-03-26: revised; 2014-03-24: received; See all versions
Short URL: https://ia.cr/2014/212
License: CC BY

BibTeX

@misc{cryptoeprint:2014/212,
      author = {Geon Heo and Seokhwan Choi and Kwang Ho Lee and Namhun Koo and Soonhak Kwon},
      title = {Remarks on the Pocklington and Padró-Sáez Cube Root Algorithm in $\mathbb F_q$},
      howpublished = {Cryptology ePrint Archive, Paper 2014/212},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/212}},
      url = {https://eprint.iacr.org/2014/212}
}