Factorization algorithm for a semiprime of 29-digits

Question

I'm looking for the fastest prime factorization algorithm for a semiprime of 29-digits. There are many factorization algorithms there, so as far as I know (my background is not maths:)the key factor is the length of the number to be factorized. In this case, it has only 29 digits. Many thanks

Answer 1

For a 29 digit semiprime number, elliptic curve factorization will suffice.

For larger semiprime numbers (around 92 digits and beyond) of a general form, the general number field sieve is the fastest factorization algorithm available.

As a practical matter, just download a program called YAFU, probably from SourceForge, for whatever platform you have. YAFU will factor semiprime numbers for you intelligently, starting with elliptic curve, and switching over to GNFS if needed. YAFU relies on GGNFS and ECM, so download those too as compiled binaries, and supply the paths to the folders the executables are in, in the yafu.ini configuration file, and you should be good to go. The configuration is straightforward, there is a ggnfs_dir and a ecm_path setting you have to set. Also choose how many threads to dedicate to the process. YAFU factors a 100 digit semiprime number (like the RSA-100 challenge number) in about an hour on my machine.

To run YAFU, simply run the yafu-Win32.exe or whatever on the command line and then type:

factor(YOUR_NUMBER_HERE)

So, to factor the RSA-100 number, you would type:

factor(1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139)

For a number of your size, 29 digits, I imagine it will take a few seconds.

If you are interested in learning the GNFS, first start by reading the Wikipedia on it to get a general overlay of the algorithm. When I was trying to learn it, I read a lot of C code, but the problem with that code is it was meant for performance, not readability. Anyways, I ended up writing an implementation of the GNFS in C#. The goal, beyond learning the GNFS, was to make the code readable, not performance, so people could read it to learn the algorithm, like I wish I had when I was learning. If you are interested, my code is on my GitHub. I also have uploaded a number of whitepapers that I read and referenced in order to help me write the application. The address is https://github.com/AdamWhiteHat/GNFS