Fast cube roots in Fp2 via the algebraic torus

Abstract

Computing cube roots in quadratic extensions of finite fields is a subroutine that arises in elliptic-curve point decompression, hash- to-curve and isogeny-based protocols. While the factorization p^2−1 = (p−1)(p+ 1) suggests a known subgroup decomposition, implementing the cube root via separate operations in the two subgroups does not beat a direct Fp2 exponentiation in practice. We propose a carefully engineered algorithm that reduces the Fp2 cube root to a single Fp addition chain and a single Lucas sequence in the algebraic torus T2(Fp). The algorithm works directly for any prime p≡1 (mod 3) (and more generally whenever p!≡8 (mod 9)), which covers all primes arising in practice. We prove correctness in all residuosity cases and implement the algorithm in Go. Benchmarks on six primes spanning pairing-based and isogeny-based cryptography show 1.6–2.3× speed-ups over direct (additionchain) exponentiations in Fp2.