International Association
for Cryptologic Research

For computing square roots in a finite field $GF(q)$ where $q - 1 = 2^n m$ for an odd integer $m$ and some integer $n$, the classic Tonelli-Shanks algorithm starts with an exponentiation (the exponent has size about $\log_2 q - n$ bits), followed by a discrete logarithm computation in the subgroup of $2^n$-th roots of unity in $GF(q)$; the latter operation has cost $O(n^2)$ multiplications in the field, which is prohibitive when $n$ is large. Bernstein proposed an optimized variant with lookup tables, leading to a runtime cost of $O((n/w)^2)$, using $w$-bit tables of cumulative size $O(2^w n/w)$. Sarkar recently improved on the runtime cost, down to $O((n/w)^{1.5})$, with the same overall storage cost. In this short note, we explore the use of a straightforward divide-and-conquer variant of the Pohlig-Hellman algorithm, bringing the asymptotic cost down to $O(n\log n)$, and further study some additional optimizations. The result appears to be competitive, at least in terms of number of multiplications, for some well-known fields such that the 224-bit field used in NIST standard elliptic curve P-224 (for which $n = 96$).