4
\$\begingroup\$

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 a = Utils.generateRandomNumber(number).add(BigInteger.valueOf(-1));

        BigInteger tmp = a.modPow(k, number);
        //a^k - 1 (mod n)
        tmp.add(BigInteger.valueOf(-1));
        //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){

    BigInteger mul = number.add(BigInteger.valueOf(-1));

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

        number = number.multiply(mul);
        mul = mul.add(BigInteger.valueOf(-1));

    }        

    return number;
}
\$\endgroup\$
1
\$\begingroup\$

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
    BigInteger a = Utils.generateRandomNumber(number).add(BigInteger.valueOf(-1));

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
    BigInteger a = Utils.generateRandomNumber(number).add(BigInteger.valueOf(-1));

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)
    tmp.add(BigInteger.valueOf(-1));

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.