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. We present a new algorithm that, for all settings where Fp2 cube roots arise in practice, reduces the cube root to operations entirely in the base field Fp via the algebraic torus and Lucas sequences. We prove correctness in all residuosity cases and implement the algorithm using the gnark-crypto open-source library. Benchmarks on six primes spanning pairing-based and isogeny-based cryptography show 1.6–2.3x speed-ups over direct (addition chain) exponentiations in Fp2. We also extend the approach to any odd n-th roots in quadratic towers.