Realistic analysis of some randomized algorithms

ABSTRACT

Many problems such as primality testing can be solved efficiently using a source of independent, identically distributed random numbers. It is therefore customary in the theory of algorithms to assume the availability of such a source. However, probabilistic algorithms often work well in practice with pseudo-random numbers; the point of this paper is to offer a justification for this fact. The results below apply to sequences generated by iteratively applying functions of the form ƒ (&khgr;) = &agr;&khgr; + &bgr; (mod p) to a randomly chosen seed x, and estimate the probability that a predetermined number of trials of an algorithm will fail. In particular, the following bounds hold: For finding square roots modulo a prime p, a failure probability of &Ogr; (log p/√p). For testing p for primality, a failure probability of &Ogr; (p-1/4+&egr;), for any &egr;>0. (In both cases, the number of trials is about 1/2 log p.) The analysis uses results of André Weil concerning the number of points on algebraic varieties over finite fields.

REFERENCES

• 1: L. Adleman, K. Manders, and G. Miller, On taking roots in finite fields, Proceedings of the l gth Annual Symposium on Foundations of Computer Science, New York: IEEE Press (1977),
• 2: L. Adleman and M. Huang, Recognizing primes in random polynomial time, to appear.
• 3: L. Blum, M. Blum, and M. Shub, A simple secure pseudorandom number generator, Proceedings of CRYPTO 82, Plenum (1982).
• 4: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 5: B. Buchberger, A theoretical basis for the reduction of polynomials to canonical forms, ACM SIGSAM Bulletin, v.10 n.3, p.19-29, August 1976 [doi>10.1145/1088216.1088219]
• 6: A.O. Gel'fond and Y.V. Linnik, Elementary Methods in the Analytic Theory of Numbers, Cambridge: MIT Press (1966).
• 7: S Goldwasser , J Kilian, Almost all primes can be quickly certified, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.316-329, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12162]
• 8: R. Hartshome, Algebraic Geometry, Springer (1977).
• 9: E. Kranakis, Primality tests, Yale University Computer Science Department Report $$345 (1984).
• 10: S. Lung, Algebra, Reading: Addison-Wesley (1971).
• 11: Markus Lauer, Canonical representatives for residue classes of a polynomial ideal, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.339-345, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806353]
• 12: D.H. Lehmer, Computer technology applied to the theory of numbers, in Studies in Number Theory, MAA Studies in Mathematics 6 (1969). {Edited by W.J. LeVeque.}
• 13: H.W. Lenstra, Jr., Factoring integers using elliptic curves, preprint, May 1986.
• 14: B. Mazur, Eigenvalues of Frobenius acting on algebraic varieties over finite fields, AMS Proceedings of Symposia in Pure Mathematics 29, pp. 231-261 (1974).
• 15: G.L. Miller, Riemann's hypothesis and tests for primality, Journal of Computer and System Sciences 13 (1976), pp. 300- 317.
• 16: B.Z. Moroz, The distribution of power residues and nonresidues, Vestnik Lenin~ad University 16 (1961), No. 19, pp. 164-169. {In Russian w~th English summary; see Gelfond and Linnik (1966) for a synopsis.}
• 17: M.O. Rabin, Probabilistic algorithm for testing primality, lournal of Number Theory 12 (1980), pp. 128-138.
• 18: G. Robin, Estimation de la fonction de Thebychef O sur le kieme hombre premier et grandes valueurs de la fonction to(n ), nombre de diviseurs de n, Acta Arithmetica 42 (1983), pp. 367-389,
• 19: W. Schmidt, Equations over Finite Fields: an Elementary Approach, Springer (1976).
• 20: R. School Elliptic curves over finite fields and the computation of square roots mod p, Mathematics of Computation 44, pp. 483-494 (1985).
• 21: D. Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics, pp. 51-70 (1972).
• 22: M Sipser, Expanders, randomness, or time versus space, Proc. of the conference on Structure in complexity theory, p.325-329, June 1986, Berkeley, California, United States
• 23: R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM Journal on Computing 6, pp. 84-85 (1977).
• 24: U. Vazirani, personal communication over coffee at STOC (1986).
• 25: A. Yao, Theory and application of trapdoor functions, Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science (1982).
• 26: O. Zarisld and P. Samuel, Commutative Algebra, Springer (1979).

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

  G. Mathematics of Computing

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Theory, Verification