A remark on the computation of cube roots in finite fields

Nozomu Nishihara; Ryuichi Harasawa; Yutaka Sueyoshi; Aichi Kudo

Paper 2009/457

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 with . 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 -th root cases with 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): PDF
Category: Foundations
Publication info: Published elsewhere. Unknown status
Keywords: cube root finite field the 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},
      url = {https://eprint.iacr.org/2009/457}
}