On the Optimality of the Binary Algorithm for the Jacobi Symbol

• Autorzy: Busch J.
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

arithmetic complexity; computational complexity; Jacobi symbol; lower bound

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 1-2
• Strony: 1--11
• Opis fizyczny: bibliogr. 18 poz.

Twórcy

autor

Busch J.

• UCLA mathematics Department, Box 951555, Los Angeles, CA 90095-1555, USA,

Bibliografia

• [1] Allender, E., Saks, M., Shparlinski, I.: A lower bound for primality, J. Comput. System Sci., 62(2), 2001, 356-366, ISSN 0022-0000.
• [2] Bach, E., Shallit, J.: Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996, ISBN 0-262-02405-5.
• [3] Bernasconi, A., Damm, C., Shparlinski, I.: Circuit and decision tree complexity of some number theoretic problems, Information and Computation, 168(2), 2001, 113-124, ISSN 0890-5401.
• [4] van den Dries, L., Moschovakis, Y. N.: Is the Euclidean algorithm optimal among its peers?, Bulletin of Symbolic Logic, 10(3), 2004, 390-418.
• [5] von zur Gathen, J.: Computing powers in parallel, SIAMJ. Comput., 16(5), 1987, 930-945, ISSN 0097-5397.
• [6] von zur Gathen, J., Seroussi, G.: Boolean circuits versus arithmetic circuits, Information and Computation, 91(1), 1991, 142-154, ISSN 0890-5401.
• [7] Hardy, G. H., Wright, E. M.: An introduction to the theory of numbers, Fifth edition, The Clarendon Press Oxford University Press, New York, 1979, ISBN 0-19-853170-2; 0-19-853171-0.
• [8] Landau, E.: Elementary number theory, Chelsea Publishing Co., New York, N.Y., 1958, Translated by J. E. Goodman.
• [9] Mansoor, Y., Schieber, B., Tiwari, P.: A lower bound for integer greatest common divisor computations, Journal of the Association for Computing Machinery, 38, 1991, 453-471.
• [10] Mansoor, Y., Schieber, B., Tiwari, P.: Lower bounds for computations with the floor operation, SIAM Journal on Computing, 20, 1991, 315-327.
• [11] McCarthy, J.: A basis for a mathematical theory of computation, in: Computer programming and formal systems, North-Holland, Amsterdam, 1963, 33-70.
• [12] Meidânis, J.: Lower bounds for arithmetic problems, Information Processing Letters, 38, 1991, 83-87.
• [13] Meyer Eikenberry, S., Sorenson, J. P.: Efficient algorithms for computing the Jacobi symbol, Journal of Symbolic Computation, 26(4), 1998, 509-523, ISSN 0747-7171.
• [14] Moschovakis, Y. N.: Arithmetic complexity, 2004, Unpublished notes.
• [15] Moschovakis, Y. N.: Recursion and complexity, in: New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. Proceedings (S. B. Cooper, B. L¨owe, L. Torenvliet, Eds.), vol. 3526/2005, Springer Lecture Notes in Computer Science, 2005, 350-357.
• [16] Plotkin, G. D.: LCF considered as a programming language, Theoret. Comput. Sci., 5(3), 1977/78, 223-255, ISSN 0304-3975.
• [17] Shallit, J. O., Sorenson, J. P.: A binary algorithm for the Jacobi symbol, ACM SIGSAM Bulletin, 27, 1993, 4-11.
• [18] Woods, A. R.: Subset sum "cubes" and the complexity of primality testing, Theoret. Comput. Sci., 322(1), 2004, 203-219, ISSN 0304-3975.