Welcome to the resource topic for
**2004/305**

**Title:**

A note on efficient computation of cube roots in characteristic 3

**Authors:**
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).

**ePrint:**
https://eprint.iacr.org/2004/305

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .