Paper 2023/828

Optimized Discrete Logarithm Computation for Faster Square Roots in Finite Fields

Thomas Pornin, NCC Group
Abstract

For computing square roots in a finite field GF(q) where q1=2nm for an odd integer m and some integer n, the classic Tonelli-Shanks algorithm starts with an exponentiation (the exponent has size about log2qn bits), followed by a discrete logarithm computation in the subgroup of 2n-th roots of unity in GF(q); the latter operation has cost O(n2) 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(2wn/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(nlogn), 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 ).

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
square roots
Contact author(s)
thomas pornin @ nccgroup com
History
2023-06-06: approved
2023-06-04: received
See all versions
Short URL
https://ia.cr/2023/828
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/828,
      author = {Thomas Pornin},
      title = {Optimized Discrete Logarithm Computation for Faster Square Roots in Finite Fields},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/828},
      year = {2023},
      url = {https://eprint.iacr.org/2023/828}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.