BPP that are not in P. Yao (1982) announced a converse result suggesting that at most a subexponential speedup is possible:

Theorem 4.1 (Yao, 1982) If there exists a uniform secure polynomial pseudorandom bit generator, then

A proof of this result appears in Boppana and Hirschfeld (1989). Several researchers, most recently Babai et al. (1991), have since improved the result by showing that the same conclusion follows from weaker hypotheses.

A detailed discussion of probabilistic complexity classes is given in Johnson (1990) and Zachos (1988).

The primality testing problem is that of determining whether an integer N is prime or composite, and the factoring problem is that of finding all the prime factors of N. These are two of the most basic computational problems in number theory.

The primality testing and factoring problems have the added practical significance of playing complementary roles in the RSA cryptosystem, which is the current best candidate for public key cryptography and for digital signatures. The practicality of constructing RSA ciphers depends on primality testing's being easy to do, whereas the security of the cipher depends on the apparent difficulty of factoring large numbers.

At present, the fastest known fully analyzed algorithms for both primality testing and factoring are probabilistic.

Theoretical and practical progress in primality testing has been rapid since 1977. Analysis of various primality testing algorithms led to study of the complexity classes described in §4.2.

Most methods of primality testing are based on variants of Fermat's little theorem, which asserts that if N is prime, then

if N does not divide a. Most composite numbers have many residues a (mod N) for which (mod N); hence a test for probable primality