You are looking at a specific version 20041125:121617 of this paper.
See the latest version.
Paper 2004/305
A note on efficient computation of cube roots in characteristic 3
Paulo S. L. M. Barreto
Abstract
The cost of the folklore algorithm for computing cube roots in $\F_{3^m}$ in standard polynomial basis is less that one multiplication, but still $O(m^2)$. Here we show that, if $\F_{3^m}$ is represented in trinomial basis as $\F_3[x]/(x^m + ax^k + b)$ with $a, b = \pm 1$, the actual cost of computing cube roots in $\F_{3^m}$ is only $O(m)$.
Metadata
- Available format(s)
- PDF PS
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- implementation
- Contact author(s)
- pbarreto @ larc usp br
- History
- 2004-11-25: revised
- 2004-11-16: received
- See all versions
- Short URL
- https://ia.cr/2004/305
- License
-
CC BY