A note on efficient computation of cube roots in characteristic 3.
Paulo S. L. M. Barreto · IACR Cryptology ePrint Archive · 2004
The cost of the folklore algorithm for computing cube roots in F3m in standard polynomial basis is less that one multiplication, but still O(m). Here we show that, if F3m is represented in trinomial basis as F3[x]/(x + ax + b) with a, b = ±1, the actual cost of computing cube roots in F3m is only O(m).