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 algorithmfinite fieldPocklington algorithmAdleman-Manders-Miller algorithmCipolla-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},
url = {https://eprint.iacr.org/2014/212}
}
