Exponential Congruences - Introduction to Cryptography with Java Applets - page 240

( p 1)/ t

x

882504362096317967796596513188946207297298097453617976463563103394591821
987874531220585600311009374053405582968213748930663530270586997171133297
840152170658259623778588348787678947522653969852413674174837135790739292
16 (mod p ).

None of these yield a residue of 1, so we conclude 2 is a generator of this safe prime p .

Java Algorithm In my PrimeGenerator class, there is a method called getSafePrime-
AndGenerator(), which finds a safe prime and a corresponding generator. There is also a

method called getSafePrime(), which finds and returns a safe prime but does not find a gen-
erator for it.

p

import java.security.*;
import java.math.*;
import java.util.*;
public class PrimeGenerator {

int minBitLength;
int certainty;
SecureRandom sr;

public PrimeGenerator(int minBitLength, int certainty, SecureRandom sr) {
//The bit length of the prime will exceed minBitLength
if (minBitLength<512) throw new IllegalArgumentException
(“Strong/Safe primes must be at least 64 bytes long.”);
this.minBitLength=minBitLength;
this.certainty=certainty;
this.sr=sr;

}

//This method returns a safe prime of form 2rt+1 where t is a large prime,
//and the factorization of r is known
//It also returns a generator for the safe prime
//The zero-th slot in the resulting array is the safe prime
//Slot 1 of the result is the generator
public BigInteger[] getSafePrimeAndGenerator() {
BigInteger[] p=new BigInteger[2];
BigInteger r=BigInteger.valueOf(0x7fffffff);
BigInteger t=new BigInteger(minBitLength-30,certainty,sr);
//p is the first prime in the sequence 2rt+1, 2*2rt+1, 2*3rt+1,...
do {
r=r.add(BigIntegerMath.ONE);
p[0]=BigIntegerMath.TWO.multiply(r).multiply(t).add(BigIntegerMath.ONE);