Realistic analysis of some randomized algorithms

摘要

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 purpose 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 f(x) =αx+β (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: 1. For finding square roots modulo a prime p, a failure probability of O(logp/√p) ). 2. For testing p for primality, a failure probability of 0(p -14+ϵ), for any ϵ > 0. (In both cases, the number of trials is about 12logp.) The analysis uses results of André Weil concerning the number of points on algebraic curves defined over finite fields.