Efficient computation of the Jacobi symbol

Niels Möller

The family of left-to-right GCD algorithms reduces input numbers by repeatedly subtracting the smaller number, or multiple of the smaller number, from the larger number. This paper…