Cryptology ePrint Archive: Report 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.

Category / Keywords: Jacobi symbol, modular inversion, Bernstein-Yang algorithm, extended Euclidean algorithm

Date: received 22 Sep 2021, last revised 30 Sep 2021

Contact author: mhamburg at rambus com

Available format(s): PDF | BibTeX Citation

Note: Apparently if you cite M\"oller's 2019 paper, it comes out as [M\"19].

Version: 20210930:135633 (All versions of this report)

Short URL: ia.cr/2021/1271


[ Cryptology ePrint archive ]