2.3 Large Primes
For instance for RSA large (i.e. at least
80 digit) primes are needed.
Usually one generated large random numbers and then tests them with a
Monte Carlo algorithm like Solovay-Strassen or Miller-Rabin for Primality.
These algorithms are fast (polynomial to the length of the number in
binary representation), but may state that n is prime when
it si not. By applying the algorithm often enough the error ratio
can be pushed below any threshold.
The other question is how many random numbers (of given size) one must test
until a prime is found. A famous result in number theory says that
the amount of primes smaller than N is
about N / ln N.
So if p is randomly chosen the likelikood for p being
prime is 1 / ln p. For a modulus of 512 bit length this means
that 1 / ln p = 1/177 (or 2/177, if restricted to odd numbers).
A yes-biased Monte Carlo algorithm is a probabilistic algorithm
for a decision problem, where a "Yes" answer is always true, whereas
a "No" answer may be wrong. A no-biased Monte Carlo algorithm is
defined accordingly.
A yes-biased Monte Carlo algorithm has error ratio EPSILON, when for any instance, for which the answer is
"Yes", it outputs the (wrong) answer "No" with a probability of at
most EPSILON.
