How to Factorize 170 digits long BigInteger

626 Views Asked by At

I need to factorize 170 digits long integer, I know that this number have 2 factors. I have tried Pollard Rho algorithm but unfortunately this is not big enough hammer to crush it. The algorithm does not end. Did I make any mistake?

import java.math.BigInteger;
import java.security.SecureRandom;

public class PollardRho {
    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE = new BigInteger("1");
    private final static BigInteger TWO = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();

    public static BigInteger rho(BigInteger N) {
        BigInteger divisor;
        BigInteger c = new BigInteger(N.bitLength(), random);
        BigInteger x = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        // check divisibility by 2
        if (N.mod(TWO).compareTo(ZERO) == 0)
            return TWO;

        do {
            x = x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        } while ((divisor.compareTo(ONE)) == 0);

        return divisor;
    }

    public static void factor(BigInteger N) {
        if (N.compareTo(ONE) == 0)
            return;
        if (N.isProbablePrime(20)) {
            System.out.println(N);
            return;
        }
        BigInteger divisor = rho(N);
        factor(divisor);
        factor(N.divide(divisor));
    }

    public static void main(String[] args) {

        BigInteger N = new BigInteger(
                "46862651776313668832684618638310007043245135907468247470585960688008180534742005269578548831878148535158738789789506710579367525183636389872513135592162572724499935530721");
        factor(N);
    }
}
0

There are 0 best solutions below