Paper 2021/1271
Computing the Jacobi symbol using BernsteinYang
Mike Hamburg
Abstract
Numbertheoretic 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 BernsteinYang righttoleft modular inversion algorithm is notable for taking constant, asymptotically subquadratic time. Righttoleft 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 righttoleft Jacobi symbol algorithm based on BernsteinYang.
Note: Replace ceil(log) with .bit_length() in code, thanks Juraj Sukop.
Metadata
 Available format(s)
 Publication info
 Preprint. Minor revision.
 Keywords
 Jacobi symbolmodular inversionBernsteinYang algorithmextended Euclidean algorithm
 Contact author(s)
 mhamburg @ rambus com
 History
 20211217: last of 3 revisions
 20210923: received
 See all versions
 Short URL
 https://ia.cr/2021/1271
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1271, author = {Mike Hamburg}, title = {Computing the Jacobi symbol using BernsteinYang}, howpublished = {Cryptology ePrint Archive, Paper 2021/1271}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1271}}, url = {https://eprint.iacr.org/2021/1271} }