Efficient Algorithms for Computing the Jacobi Symbol

We present two new algorithms for computing the Jacobi Symbol: the right-shift and left-shiftk-ary algorithms. For inputs of at mostnbits in length, both algorithms takeO(n2/logn) time andO(n) space. This is asymptotically faster than the traditional algorithm, which is based in Euclidʹs algorithm for computing greatest common divisors. In practice, we found our new algorithms to be about twice as fast for inputs of 100 to 1000 decimal digits in length. We also present parallel versions of both algorithms for the CRCW PRAM. One version takesOε(n/ log logn) time usingO(n1 + ε) processors, giving the first sublinear parallel algorithms for this problem. The other version takes polylog time using a subexponential number of processors.