Czasopismo
2007
|
Vol. 76, nr 1-2
|
1-11
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
1-11
Opis fizyczny
bibliogr. 18 poz.
Twórcy
autor
- UCLA mathematics Department, Box 951555, Los Angeles, CA 90095-1555, USA, jbusch@math.ucla.edu
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS5-0009-0030