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

Contact author: harasawa at cis nagasaki-u ac jp

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20090920:051112 (All versions of this report)

Discussion forum: Show discussion | Start new discussion