A binary algorithm for the Jacobi symbol
Jeffrey O. Shallit, Jonathan Sorenson · ACM SIGSAM Bulletin · 1993
We present a new algorithm to compute the Jacobi symbol, based on Stein's binary algorithm for the greatest common divisor, and we determine the worst-case behavior of this algorithm. Our implementation of the algorithm runs approximately 7--25% faster than traditional methods on inputs of size 100--1000 decimal digits.