Factorization Techniques - Introduction to Cryptography with Java Applets - page 228

E XAMPLE .

= 9090909091. We apply the Monte Carlo method to obtain the values
shown in Table 12.4.

Let n

TABLE 12.4

m i

i (m i - m i /2 ,n)

0 44016065

1 4887155761

2 4763918935 1

3 842766808

4 1750315397 11

E XAMPLE . Let n = 992387659879678689176986897665716567855813467857777. We
apply the Monte Carlo method to obtain the values shown in Table 12.5.

TABLE 12.5

i m i (m i - m i /2 ,n)

0 169995877

1 28898598196999130

2 835128977751601367248137220756901 57

Java Algorithm The monteCarloFactor() method will be quite interesting to write. We
will make an array of integers to hold the generated sequence, and compute gcd's at every
other iteration of the number-generating loop. The code to do this is elementary. (This
method is in the BigIntegerMath class):

//Monte Carlo factorization method returns a Monte Carlo factor.
//An array holds a sequence of random numbers; must specify max
//size of this array.
//This puppy returns null if no factor is found.
public static BigInteger monteCarloFactor(BigInteger n,int maxArraySize)
throws IllegalArgumentException, ArrayIndexOutOfBoundsException {
if (n.compareTo(THREE)<=0)
throw new IllegalArgumentException(“Number to factor must be > 3”);
BigInteger[] m=new BigInteger[maxArraySize];
m[0]=BigInteger.valueOf(new Random().nextInt());
BigInteger g;
for (int i=1;i<maxArraySize;i++) {
m[i]=m[i-1].multiply(m[i-1]).add(ONE).mod(n);