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

BigInteger residue=lnr(BigInteger.valueOf(rand.nextInt()),n);
BigInteger test=residue.subtract(ONE);
BigInteger gcd=test.gcd(n);
while (true) {
while (gcd.equals(ONE)) {
power=power.add(ONE);
residue=residue.modPow(power,n);
test=residue.subtract(ONE);
gcd=test.gcd(n);

}
if (gcd.equals(n)) {
power=BigInteger.valueOf(1);
residue=lnr(BigInteger.valueOf(rand.nextInt()),n);
test=residue.subtract(ONE);
gcd=test.gcd(n);
} else return gcd;

}

}

1 method can be used to break cryptosystems based on factoring num-
bers having large prime factors if the primes are chosen carelessly. To prevent this method
from factoring quickly, one must make sure that the choice of a prime

The Pollard p

p must be such that

p 1 has at least one large prime factor. For example, consider the following prime:

p = 160086307116559738155869925798757514626756457565007398646711114857005

992922967078590696196618658161690735876437589642027120745407208793588072
404971617007494843354135377095406066154855880767615610812537786121677226
656934787295293329889991101773874178363226192550806087278026993983201987
753863431668129069694725023374409414275815875828834913374670967078348380
060934470394466978765779646756545675424549350157457563271478245865405680
761395848801899028763255590217026083243137987131686080581096674871056010
581499513879026589855942403498079792835159647491344925369568016515800543
448680025803391561534522694855761493401748918989590240396787824784555716
446448873404044136201133055019564546002121091038978073635688462008895936
295056689750153498900363988015318027982295262581227520000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000
000001.
If you run the Pollard

p 1 method on a large integer having this prime p as a factor, p

will be found in only 399 iterations! Why? It turns out that this particular prime p = 399! +

1. Though these primes are rare, there are many other primes q not specifically of this form

such that q 1 divides k ! for a relatively small value of k . To ensure this does not happen,

we must choose such primes such that q 1 has a large prime factor, forcing k to also be

large.
I have written an applet (called TestFactorApplet), which demonstrates both the Monte
Carlo method, and the Pollard p 1 method of factorization. You enter an integer, then