Paper 2021/1271

Computing the Jacobi symbol using Bernstein-Yang

Mike Hamburg

Abstract

Number-theoretic algorithms often need to calculate one or both of two related quantities: modular inversion and Jacobi symbol. These two functions seem unrelated at first glance, but in fact the algorithms for calculating them are closely related: they can both be calculated either by variants of Euclid's GCD algorithm, or when the modulus is prime, by exponentiation. As a result, an implementation of one algorithm can often be adapted to compute the other instead, or they can even be calculated together in a batch. The Bernstein-Yang right-to-left modular inversion algorithm is notable for taking constant, asymptotically subquadratic time. Right-to-left algorithms are tricky to adapt for the Jacobi symbol, because they do not consider the signs of the values being operated on. But the Jacobi symbol is defined only on positive integers, and the rules for computing it need corrections if negative integers are introduced. In this short paper, we show how to overcome this difficulty and produce a right-to-left Jacobi symbol algorithm based on Bernstein-Yang.

Note: Replace ceil(log) with .bit_length() in code, thanks Juraj Sukop.

Metadata
Available format(s)
PDF
Publication info
Preprint. Minor revision.
Keywords
Jacobi symbolmodular inversionBernstein-Yang algorithmextended Euclidean algorithm
Contact author(s)
mhamburg @ rambus com
History
2021-12-17: last of 3 revisions
2021-09-23: received
See all versions
Short URL
https://ia.cr/2021/1271
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1271,
      author = {Mike Hamburg},
      title = {Computing the Jacobi symbol using Bernstein-Yang},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1271},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1271}},
      url = {https://eprint.iacr.org/2021/1271}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.