International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: A note on efficient computation of cube roots in characteristic 3

Authors:
Paulo S. L. M. Barreto
Download:
URL: http://eprint.iacr.org/2004/305
Search ePrint
Search Google
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)$.
BibTeX
@misc{eprint-2004-12271,
  title={A note on efficient computation of cube roots in characteristic 3},
  booktitle={IACR Eprint archive},
  keywords={implementation},
  url={http://eprint.iacr.org/2004/305},
  note={ pbarreto@larc.usp.br 12747 received 15 Nov 2004, last revised 25 Nov 2004},
  author={Paulo S. L. M. Barreto},
  year=2004
}