programmatically factorize a large number

Question

Alright, so I have a huge number f. This number is just over 100 digits long, actually. I know that the factors are of approximately the same size.

If I have limited resources and time, what language and algorithm should I use? I am including the length of time to code the algorithm in the restricted time.

Thoughts?

EDIT: By limited, I mean in the least amount of time possible.

Answer 1

The state-of-the-art prime factorization algorithm is the quadratic sieve and its variants. For numbers larger than 100 digits, the number sieve becomes more efficient.

There's an open-source implementation of it here. It's able to factor a 100 digit number into two roughly equal primes in only 4 hours on a 2.2 GHz AMD Althon.

So there's the algorithm and a sample implementation. That might be enough to give you ideas or get you started.

Answer 2

This sounds like a good exercise (and possibly a rare good example) for cloud computing. This should be easy to run parallel processing against. Divide your pools of factors across each of your processes.

Something like this may prove helpful: http://blog.controlgroup.com/2010/10/13/hadoop-and-amazon-elastic-mapreduce-analyzing-log-files/ More details at http://en.wikipedia.org/wiki/Apache_Hadoop#Hadoop_on_Amazon_EC2.2FS3_services .

(In the past month, I had watched a nice video demonstration of doming something similar to what I'm suggesting here - but of course, now I can't find the link.)

Especially if you don't need to do this programatically, take a look at http://www.alpertron.com.ar/ECM.HTM . (Linked to from http://en.wikipedia.org/wiki/Quadratic_sieve.) Pay particular attention to the notes under "Factoring a number in several machines" on the first link. (As the source code is available, you could run this is a programatically distributed fashion as well, using Hadoop or the like.)

Answer 3

while (x < Number) {
    if ((Number % x) == 0 ) { 
        cout << x << "*" << Number/x << endl;
        ++x;
    }  
    else ++x;
}