CODEWITHSUNDEEP
javaalgorithmbigintegerfactorization
vawco112
vawco112

Reputation: 3

Pollard Rho can't find factor

So I am attempting to create a Pollard's Rho Factoring Algorithm in Java using the BigInteger class to support very large integers. The code mostly works but cannot find a factor for 4 or 8 (which should be 2). Currently I have capped it to cycle through the algorithm 10,000,000 times and still it can't find 2 as a factor. a is generated randomly (limited between 0 and 1000). Is this just a flaw in the Pollard Rho Algorithm or is there a mistake somewhere in the implementation?

The n being passed is 4

The initial a is calculated as a random the same way in the below code, between 0 and 1000

The sqrt(n) method returns the floor of the square root of n (in this case sqrt(sqrt(4)) = 1

I printed count at the end to make sure it was actually iterating how many times it was supposed to.

private static BigInteger PollardRho (BigInteger a, BigInteger n) {

    BigInteger gcd = BigInteger.ZERO;

    BigInteger Tort = a;

    BigInteger Hare = a;

    BigInteger count = BigInteger.ZERO;

    BigInteger iterationLim = (sqrt(sqrt(n))).multiply(BigInteger.valueOf(10000000));

    while (count.compareTo(iterationLim)!=0)
    //makes sure that the algorithm does not surpass (4th root of n)*10000000 iterations.
    {

    Tort = ((Tort.pow(2)).add(BigInteger.ONE)).mod(n);

    //System.out.println("Tort: "+Tort);

    Hare = (((Hare.pow(2)).add(BigInteger.ONE).pow(2)).add(BigInteger.ONE)).mod(n);

    //System.out.println("Hare: "+Hare);

    gcd = (Tort.subtract(Hare)).gcd(n);

    //System.out.println("gcd: "+gcd);

    if (gcd.compareTo(BigInteger.ONE) != 0 && gcd.compareTo(n) != 0)
    {
    //  System.out.println("took if, gcd = "+gcd);

        return gcd;
    }

    if (gcd.compareTo(n) == 0)
    {
        a = (BigInteger.valueOf((long) (1000*Math.random())));
        Tort = a;
        Hare = a;
    }

    count = count.add(BigInteger.ONE);

    }

    System.out.println(count);
    return n;


}

Upvotes: 0

Views: 1129

Answers (1)

Henry
Henry

Reputation: 43738

Pollard's Rho method usually can only split numbers composed of different primes. It fails most of the time for numbers that are prime powers. 4 and 8 are powers of a single prime 2 and therefore unlikely to be split by this method.

The method works by iterating a random function f(x) mod n, in this case f(x) = x^2+1 is used, but other functions work as well. The trick is that f(x) mod p where p is a prime factor of n enters a cycle after a different number of iterations for different primes. So f(x) mod p1 may already be in a cycle, f(x) mod p2 not yet. The gcd calculation is then able to find the factor p1.

It is btw. very easy to check if a number is a proper power of an integer. Just calculate the 2nd, 3rd, 4th, ... root and check if it is an integer.

Upvotes: 4

Related Questions