### 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)$.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Keywords
implementation
Contact author(s)
pbarreto @ larc usp br
History
2004-11-25: revised
See all versions
Short URL
https://ia.cr/2004/305

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.