On the optimality of the binary algorithm for the Jacobi symbol
We establish lower bounds on the complexity of computing the following number-theoretic functions and relations from piecewise linear primitives: (i) the Legendre and Jacobi symbols, (ii) pseudoprimality, and (iii) modular exponentiation. As a corollary to the lower bound obtained for (i), an algorithm of Shallit and Sorenson is optimal (up to a multiplicative constant).
jacobi symbol lower bounds arithmetic complexity computational complexity