  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 describes how to extend any such algorithm
to compute the Jacobi symbol, using a single table lookup per reduction. For
both quadratic time GCD algorithms (Euclid, Lehmer) and subquadratic algorithms
(Knuth, Sch\"onhage, M\"oller), the additional cost is linear, roughly one
table lookup per quotient in the quotient sequence. This method was used for
the 2010 rewrite of the Jacobi symbol computation in GMP.
