### A remark on the computation of cube roots in finite fields

Nozomu Nishihara, Ryuichi Harasawa, Yutaka Sueyoshi, and Aichi Kudo

##### Abstract

We consider the computation of cube roots in finite fields. For the computation of square roots in finite fields, there are two typical methods; the Tonelli-Shanks method and the Cipolla-Lehmer method. The former can be extended easily to the case of $r$-th roots, which is called the Adleman-Manders-Miller method, but it seems to be difficult to extend the latter to more general cases. In this paper, we propose two explicit algorithms for realizing the Cipolla-Lehmer method in the case of cube roots for prime fields $\mathbb{F}_{p}$ with $p \equiv 1 \ ({\rm mod} \ {3})$. We implement these methods and compare the results.

Note: The full version of this paper, named Root computation in finite fields", appears in IEICE Trans. Fundamentals, Vol. E96-A, No. 6, pp. 1081 -- 1087, 2013, which includes a generalization of the Cipolla-Lehmer method to $r$-th root cases with $r$ prime. We add only the information on the publication of the full version of this paper at the footnote in p.1. The others is the same as the previous version.

##### Metadata
Available format(s)
Category
Foundations
Publication info
Published elsewhere. Unknown status
Keywords
cube rootfinite fieldthe Tonelli-Shanks method
Contact author(s)
harasawa @ cis nagasaki-u ac jp
History
2013-09-13: revised
2009-09-20: received
See all versions
Short URL
https://ia.cr/2009/457
License

CC BY

BibTeX

@misc{cryptoeprint:2009/457,
author = {Nozomu Nishihara and Ryuichi Harasawa and Yutaka Sueyoshi and Aichi Kudo},
title = {A remark on the computation of cube roots in finite fields},
howpublished = {Cryptology ePrint Archive, Paper 2009/457},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/457}},
url = {https://eprint.iacr.org/2009/457}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.