Efficient Algorithms for Computing the Jacobi Symbol.
J. Symb. Comput., 26 (4):
509-523 (1998)Abstract
We present two new algorithms for computing the Jacobi Symbol: the right-shift and left-shift k-ary algorithms. For inputs of at most n bits in length, both algorithms take $O(n^2 / log n)$ time and $O(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 takes $O_\epsilon(n / n)$ time using $O(n^1+\epsilon)$ processors, giving the first sublinear parallel algorithms for this problem. The other version takes polylog time using a subexponential number of processors.