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

**Category / Keywords: **implementation

**Date: **received 15 Nov 2004, last revised 25 Nov 2004

**Contact author: **pbarreto at larc usp br

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20041125:121617 (All versions of this report)

**Short URL: **ia.cr/2004/305

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]