Quadratic Ciphers - Introduction to Cryptography with Java Applets - page 193

FIGURE 10.1
This applet also allows you to generate a probable prime using what is called the
Rabin-Miller test. We have been using the constructor provided in Java from the BigInte-
ger class:
public BigInteger(int bitLength, int certainty, Random r).
This constructor generates random BigIntegers of the specified bitlength, until one passes
a primality test for a certain number of trials. The probability that this number is prime is
1 (1/2) certainty .
This constructor does not use the Rabin Miller primality test. However, we will cover the
Rabin-Miller test in the chapter on primality testing. This applet also allows you to gener-
ate what are called safe primes, suitable for other types of cryptosystems. The PrimeGen-
erator class has a getSafePrimeAndGenerator() method, and a getSafePrime() method. Look
in the chapter on exponential congruences for the definitions of safe prime, and generator.
There are other properties a prime may have that would make it vulnerable to certain fac-
toring algorithms; see the chapter on factorization techniques for more information.
Square Root Problem The Chinese Remainder Theorem can help an adversary if
Rabin is used to send the same message to multiple entities. Suppose someone wants to