Computing the Jacobi symbol using Bernstein-Yang

Mike Hamburg

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 symbol modular inversion Bernstein-Yang algorithm extended 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: 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}
}