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

BibTeX

@misc{cryptoeprint:2004/305,
      author = {Paulo S.  L.  M.  Barreto},
      title = {A note on efficient computation of cube roots in characteristic 3},
      howpublished = {Cryptology ePrint Archive, Paper 2004/305},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/305}},
      url = {https://eprint.iacr.org/2004/305}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.