Cryptology ePrint Archive: Report 2009/457

A remark on the computation of cube roots in finite fields

Nozomu Nishihara and Ryuichi Harasawa and 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.

Category / Keywords: foundations / cube root, finite field, the Tonelli-Shanks method,

Date: received 17 Sep 2009, last revised 13 Sep 2013

Contact author: harasawa at cis nagasaki-u ac jp

Available format(s): PDF | BibTeX Citation

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.

Version: 20130913:091306 (All versions of this report)

Short URL: ia.cr/2009/457

Discussion forum: Show discussion | Start new discussion