# Pollard p - 1 implementation

I'm trying to implement the Pollard p - 1 algorithm seen here, in Java. It has a C implementation here. I am using it for numbers without any smaller factors so trial factorisation isn't needed. My implementation can factor numbers such as 15236506168104630133 but it takes around ten minutes. I also would like it to factor number of up to 30 digits with it. Is there any improvements I can make?

public static void factorise(BigInteger number){

BigInteger b = BigInteger.valueOf(10);
//b!
BigInteger k = Utils.factorial(b);

while(true){

//random number a from number 0 to n-2

BigInteger tmp = a.modPow(k, number);
//a^k - 1 (mod n)
//gcd(a^k - 1 (mod n), number);
BigInteger gcd = tmp.gcd(number);

if(gcd.compareTo(BigInteger.ONE) > 0){

if(gcd.isProbablePrime(100)){
System.out.println("Factor:d " + gcd);

number = number.divide(gcd);

}

if(number.compareTo(BigInteger.ONE) == 0){
System.out.println("done");
return;
}

if(number.isProbablePrime(10)){
System.out.println("Factor: " + number);
return;
}

}

}

}

public static BigInteger generateRandomNumber(BigInteger number){

BigInteger random;
do {
random = new BigInteger(number.bitLength(), new SecureRandom());
} while (random.compareTo(number) >= 0);

return random;

}

public static BigInteger factorial(BigInteger number){

while(mul.compareTo(BigInteger.valueOf(1)) != 0){

number = number.multiply(mul);

}

return number;
}


I really really hate when the comments (which are supposed to help) don't agree with the code. Because now you don't know which is correct (the code or the comments).

    //random number a from number 0 to n-2


When writing comments. DO NOT put a comment for each obvious line of code. The code describes itself I don't need you to tell me what the line of code does. I can actually read code (as can everybody that will read your code).

When you write comments describe the algorithm that your code is trying to implement (preferably with a link to a static page that will never move (wikipidia) that not only describes the algorithm but what its trying to do (or put it in the comments at the top of a chunk of code). Describe WHY you are using the algorithm and what the final result will be.

### Code:

    //random number a from number 0 to n-2


If this actually generates a random number in that range then I would seriously kick the implementer of generateRandomNumber for generating an initial range of [1..(number-1))

This comment is even stranger:

    BigInteger tmp = a.modPow(k, number);
//a^k - 1 (mod n)


Really. Not sure what the heck is happening here.

What is it with all the usless white space.

            }

}

}

}


Maybe I should kick the implementor of generateRandomNumber

public static BigInteger generateRandomNumber(BigInteger number){


That is not doing what the name suggests it is doing.

Yep sure the loop is going to work:

do {
random = new BigInteger(number.bitLength(), new SecureRandom());
} while (random.compareTo(number) >= 0);


But why have the loop. Why not generate a random one smaller than the max than add one.

Also why are you creating a new random number generator on each iteration new SecureRandom(). You just create than once (in the entire life cycle of the program) then use the instance every time.