Welcome to the resource topic for 2023/828
Title:
Optimized Discrete Logarithm Computation for Faster Square Roots in Finite Fields
Authors: Thomas Pornin
Abstract: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).
ePrint: https://eprint.iacr.org/2023/828
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .