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

if (minBitLength<512) throw new IllegalArgumentException
(“Strong/Safe primes must be at least 64 bytes long.”);
//Set the values
this.minBitLength=minBitLength;
this.certainty=certainty;
this.sr=sr;
}
//This method finds and returns a strong prime
public BigInteger getStrongPrime() {
//The strong prime p will be such that p+1 has a large prime factor s
BigInteger s=new BigInteger(minBitLength/2-8,certainty,sr);
//t will be a large prime factor of r, which follows
BigInteger t=new BigInteger(minBitLength/2-8,certainty,sr);
BigInteger i=BigInteger.valueOf(1);
//p-1 will have a large prime factor r
//r is the first prime in the sequence 2t+1, 2*2t+1, 2*3t+1,...
BigInteger r;
do {
r=BigIntegerMath.TWO.multiply(i).multiply(t).add(BigIntegerMath.ONE);
i=i.add(BigIntegerMath.ONE);
} while (!r.isProbablePrime(certainty));
BigInteger z=s.modPow(r.subtract(BigIntegerMath.TWO),r);
BigInteger pstar=BigIntegerMath.TWO.multiply(z).multiply(s).
subtract(BigIntegerMath.ONE);
BigInteger k=BigInteger.valueOf(1);
//The strong prime p is the first prime in the sequence 2rs+p*, 2*2rs+p*,
//2*3rs+p*,...
BigInteger p=BigIntegerMath.TWO.multiply(r).multiply(s).add(pstar);
while (p.bitLength()<=minBitLength) {
k=k.multiply(BigIntegerMath.TWO);
p=BigIntegerMath.TWO.multiply(k).multiply(r).multiply(s).add(pstar);
}
while (!p.isProbablePrime(certainty)) {
k=k.add(BigIntegerMath.ONE);
p=BigIntegerMath.TWO.multiply(k).multiply(r).multiply(s).add(pstar);
}
return p;
}
}
An applet that tests the getStrongPrime() method follows; it is called TestPrimeGenera-
torApplet, and can be run from the topic's website. A screen shot of the applet is shown in
Figure 10.1.