You are looking at a specific version 20090920:051112 of this paper.
See the latest version.
Paper 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.
Metadata
- Available format(s)
- PDF PS
- Category
- Foundations
- Publication info
- Published elsewhere. Unknown where it was published
- 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