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 \F3m in standard polynomial basis is less that one multiplication, but still O(m2). Here we show that, if \F3m is represented in trinomial basis as \F3[x]/(xm+axk+b) with a,b=±1, the actual cost of computing cube roots in \F3m 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},
      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.