On the Optimality of the Binary Algorithm for the Jacobi Symbol

Article type: Research Article

Authors: Busch, J.

Affiliations: Department of Mathematics, University of California, Los Angeles, Los Angeles, CA, USA. E-mail: [email protected]

Abstract: 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).

Keywords: arithmetic complexity, computational complexity, Jacobi symbol, lower bounds

Journal: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 1-11, 2007