Software factorize a large number

Question

Good, so I have a huge amount of f . In fact, this number is just over 100 digits. I know that factors are about the same size.

If I have limited resources and time, what language and algorithm should I use? I include time to encode the algorithm for a limited time.

Thoughts?

EDIT: Limited, I mean for a minimal amount of time.

Answer 1

The modern simple factorization algorithm is a quadratic sieve and its variants. For numbers exceeding 100 digits, the number of sieves becomes more efficient.

There is an open source implementation implemented here . It is capable of encoding a 100-digit number into two roughly equal prime numbers in only 4 hours at 2.2 GHz AMD Althon .

So, there is an algorithm and an example implementation. This may be enough to give you ideas or get started.

Answer 2

It sounds like a good exercise (and perhaps a rare good example) for cloud computing. It should be easy to do parallel processing. Separate your factor pools in each of your processes.

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

(Last month, I watched a good video demonstration of a dome of something similar to what I offer here, but of course, now I can not find the link.)

Especially if you do not need to do this programmatically, see http://www.alpertron.com.ar/ECM.HTM . (Associated with http://en.wikipedia.org/wiki/Quadratic_sieve . Pay particular attention to the notes in the section “Factoring numbers on multiple machines” at the first link. (Since the source code is available, you can also run this in a programmatically distributed way, using Hadoop or the like.)

Answer 3

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