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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.