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

Now, we compute z , the lnr of s r 2 modulo r :

z =
665230492072090237201496662581252085144747143014640731643715847110536584
592217084417720567412260139505217601163389933696724796030966764997614576
5260549183

We compute p * as 2 zs 1:

p * =

346084307903560664425684232051486131077315397498633595581688753937826631
433322997849280623926140157753141972793817951619368163028361404889048627
525470705306956391991968534559962944356650024630432157045548591633214550
857822086145412115926942830031833676001801967113277394757571799217642094
28697654507474370737
We search now for the first prime p of the form p * + 2 krs , where here k starts with the

value 1. This yields a strong prime, and, in this case, we get:

p =
136859550991023357674233837751193444637145211672745580838508211454534324
823686210424604005719046718052981484190707562992713417956940416543355152
315219159854859002395777579635185385039269578229009584384066590554210488
182334714799737615710384650453125076807810092764555005612188062536100529
729582192738972213180427

Java Algorithm I have created a PrimeGenerator class for the purpose of generating
strong primes. One creates a PrimeGenerator object, then calls a getStrongPrime() method.
The primes generated by this method are of sufficient size and quality to thwart modern
factorization methods.

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

//To find primes, we first specify the minimum bit length
//The methods will produce primes 1 to 3 bits larger than requested, but never
// smaller
int minBitLength;

//certainty is the number of primality tests to pass
int certainty;

SecureRandom sr;

public PrimeGenerator(int minBitLength, int certainty, SecureRandom sr) {
//The bit length of the prime will exceed minBitLength