Paper 2026/392

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 $\mathbb{F}_{p^2}$ exponentiation in practice. We propose a carefully engineered algorithm that reduces the $\mathbb{F}_{p^2}$ cube root to a single $\mathbb{F}_p$ addition chain and a single Lucas sequence in the algebraic torus $\mathbb{T}_2(\mathbb{F}_p)$. The algorithm works directly for any prime $p \equiv 1 \pmod 3$ (and more generally whenever $p \not \equiv 8 \pmod 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$\times$ speed-ups over direct (addition chain) exponentiations in $\mathbb{F}_{p^2}$.