A note on efficient computation of cube roots in characteristic 3

Paulo S.  L.  M.  Barreto

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

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},
      url = {https://eprint.iacr.org/2004/305}
}