Pseudoprime

From Prime-Wiki
Jump to: navigation, search

A pseudoprime is a composite number which passes some probabilistic primality tests.

Thus, when speaking about pseudoprimes, one has to specify the test performed.

For example, a strong pseudoprime is a composite number that passes one iteration the Miller-Rabin pseudoprimality test.

Pseudoprimes are useful in many areas of computing where primes need to be generated quickly. One example of such a field is in the RSA encryption system, where each party needs to generate two large primes, possibly with hundreds of decimal digits. Actually testing candidates for primality is impractibly slow; however probabilistic primality tests can rapidly generate numbers which are "probably prime". The term "probably" is not to be taken lightly; a number which passes only 100 iterations of the Miller-Rabin test, for example, has a probability of only [math]{1/4}^{100}[/math] of being composite, which is less than [math]10^{-60}[/math].

External links