CODEWITHSUNDEEP
javacryptographyrsafactorization
bykodlak
bykodlak

Reputation: 21

Faster prime factorization for huge BigIntegers in Java

so I'm working on a java code right now. I've gotten it working totally fine, however the point of the assignment is to make it factorize big number (over 30 digits). It does that, however it can take over 15 minutes for it to do it, which is no good. My professor assures me that the algorithm I am using will work for numbers up to 2^70 and should do it in about five minutes. I have been trying to come up with a way to do it (incrementing by 2 instead of 1, etc), but I can't really seem to figure out how to get it to move quicker without skipping some factors. Any ideas? I also figured that the Elliptic Curve method would be better, but he told me to not deal with that right now.

Here is my code (ps, the sqrt is my own function but I am sure it is working): 

public String factorizer(BigInteger monster){
    System.out.println("monster =" + monster); 
    String factors = "";  
    BigInteger top = maths.monsterSqrt(monster);   
    if(monster.mod(two).equals(0));
        BigInteger jump = two;
    for(BigInteger bi = two; bi.compareTo(top) <= 0; bi = bi.add(jump)){
        while(monster.mod(bi).equals(zero)){
            factors +=  "+" + bi + ""; 
            monster = monster.divide(bi); 
            jump = one; 
        }
    }
    if(monster.compareTo(BigInteger.ONE) == 1){
        factors  += "+" + monster; 
    } 
    return factors; 
}

Upvotes: 2

Views: 9942

Answers (3)

user448810
user448810

Reputation: 17866

Here is my version of integer factorization by trial division:

public static LinkedList tdFactors(BigInteger n)
{
    BigInteger two = BigInteger.valueOf(2);
    LinkedList fs = new LinkedList();

    if (n.compareTo(two) < 0)
    {
        throw new IllegalArgumentException("must be greater than one");
    }

    while (n.mod(two).equals(BigInteger.ZERO))
    {
        fs.add(two);
        n = n.divide(two);
    }

    if (n.compareTo(BigInteger.ONE) > 0)
    {
        BigInteger f = BigInteger.valueOf(3);
        while (f.multiply(f).compareTo(n) <= 0)
        {
            if (n.mod(f).equals(BigInteger.ZERO))
            {
                fs.add(f);
                n = n.divide(f);
            }
            else
            {
                f = f.add(two);
            }
        }
        fs.add(n);
    }

    return fs;
}

This code is explained in an essay on my blog, where there is also an explanation of Pollard's rho algorithm, which may be more suitable for factoring big integers.

By the way, 30 digits is not a particularly big factorization problem these days. Anything more than a few seconds is too long.

Upvotes: 6

OldCurmudgeon
OldCurmudgeon

Reputation: 65811

Not sure why you are returning a String!

This works for me. Note that it compares i with n / i and n = n / i each time around:

// Memoization of factors.
static Map<BigInteger, List<BigInteger>> factors = new HashMap<>();
private static final BigInteger TWO = BigInteger.ONE.add(BigInteger.ONE);

public static List<BigInteger> factors(BigInteger n, boolean duplicates) {
  // Have we done this one before?
  List<BigInteger> f = factors.get(n);
  if (f == null) {
    // Start empty.
    f = new ArrayList<>();
    // Check for duplicates.
    BigInteger last = BigInteger.ZERO;
    // Limit the range as far as possible.
    for (BigInteger i = TWO; i.compareTo(n.divide(i)) <= 0; i = i.add(BigInteger.ONE)) {
      // Can have multiple copies of the same factor.
      while (n.mod(i).equals(BigInteger.ZERO)) {
        if (duplicates || !i.equals(last)) {
          f.add(i);
          last = i;
        }
        // Remove that factor.
        n = n.divide(i);
      }
    }
    if (n.compareTo(BigInteger.ONE) > 0) {
      // Could be a residue.
      if (duplicates || n != last) {
        f.add(n);
      }
    }
    // Memoize.
    factors.put(n, f);
  }
  return f;
}

Upvotes: 0

Arend
Arend

Reputation: 2423

When you divide your monster by a prime factor, you should also adjust top accordingly. As it is, the outer loop will always run up to the square root of the original number, in increments of 1 or 2, which for a 30-digit number takes in the order of 10^15 steps... it's to be wondered that you are done in only 15 minutes!

If your monster number has very large prime factors (say it is a prime itself), then you can forget about good performance in any case.

Note that your example code does the increments wrong: if the original number is not even then jump will always remain two, meaning that you only investigate even factors and hence will not find any.

Upvotes: 2

Related Questions