Beginners Guide to NFS factoring using GGNFS and MSIEVE
by Jeff Gilchrist
--------------------------------------------------------------------------------
Last Updated: April 14, 2009
This guide is designed to help experienced computer users who are beginners to factoring numbers larger than 100 digits with the Number Field Sieve (NFS) algorithm. It will guide you on how to use the GGNFS and MSIEVE software tools to accomplish this. For numbers smaller than 100 digits, the Quadratic Sieve (QS) should be used with such programs as MSIEVE or YAFU.
This guide shows an example of how to factor the following 121 digit integer using the General Number Field Sieve (GNFS):
8996941959382577683409613171454174240738275788293429353288678806601664747011544951714674576925430397444054300751795281737
Step 1 - Download the Required Software
Obtain the GGNFS binaries. If you are using Windows you will need version SVN 339 or newer, pre-compiled GGNFS binaries can are available from this web site. If you are using Linux or some form of UNIX, you need to download the source code and compile it yourself, or use a 64bit Linux Binary.
Obtain the latest MSIEVE binaries and overwrite the msieve that comes with ggnfs. If you are using Windows, pre-compiled MSIEVE binaries can are available from this web site. If you are using Linux or some form of UNIX, you need to download the source code and compile it yourself. NOTE: To enable the advanced polynomial selection code you need to compile msieve with 'make GMP=1' or 'make ECM=1', otherwise the old code will be used.
For Windows users, you will need a UNIX-like environment to run the perl scripts and tools for factoring. Download and install CYGWIN on your Windows system. The CYGWIN setup program can be downloaded here. During the install at the "Select Packages" screen, scroll down until you see the "Perl" setting. It will probably say "Default" beside it. Click on "Default" until it says "Install" and then click on the "Next" button to continue installation. This will ensure that the Perl package is installed which is needed by factMsieve.pl. After installing CYGWIN, double click on the cygwin icon to launch the cygwin shell environment. The shell will place you in your new home directory which will be /home/username where username is the name of Windows user account you are currently logged in with.
If you need help with GGNFS in general, you can try searching for an answer or posting in the GGNFS Message Board.
NOTE: If you are not capable of completing the stages of Step 1, stop now, you probably do not have the technical skill to complete the rest.
Step 2 - Install and Configure the Software
After you have downloaded or compiled the GGNFS binaries, copy them to a directory on your system such as: /home/jeff/ggnfs
The GGNFS distribution contains an older version of msieve, you should now copy your newly downloaded or compiled msieve binary over the old one in: /home/jeff/ggnfs
Your ggnfs directory (/home/jeff/ggnfs) should now contain the following files (UNIX users will not have an .exe extension for the executables):
def-nm-params.txt
def-par.txt
factLat.pl
factMsieve.pl
ggnfs-doc.pdf
gnfs-lasieve4I12e.exe
gnfs-lasieve4I13e.exe
gnfs-lasieve4I14e.exe
gnfs-lasieve4I15e.exe
gnfs-lasieve4I16e.exe
makefb.exe
matbuild.exe
matprune.exe
matsolve.exe
msieve.exe
pol51m0b.exe
pol51m0n.exe
pol51opt.exe
polyselect.exe
procrels.exe
sieve.exe
sqrt.exe
Change to your ggnfs directory (cd /home/jeff) and create a working directory for your factoring job (md example). In this case we have created /home/jeff/ggnfs/example
Windows users will need to make sure execute permissions are set properly for the ggnfs/msieve binaries in cygwin. In your ggnfs directory run the following command:
chmod 755 *.exe *.pl
Use your favourite text editor to edit the factMsieve.pl file. Windows users may want to try Notepad++ or Crimson Editor. You will need to modify several lines in factMsieve.pl to configure the script for your system. Make the changes listed below.
Change lines 3-4 from:
# The path where the binaries are:
$GGNFS_BIN_PATH="../../ggnfs/bin";
to:
# The path where the binaries are:
$GGNFS_BIN_PATH="..";
Change line 54 from:
$NUM_CPUS=1;
to whatever the # of CPUs you want to use for the factoring. On a dual-core system you can choose 1 or 2, on a quad-core 1, 2, 3, 4:
$NUM_CPUS=2;
If you want the software to run at low priority so it does not interfere with other programs running on the system, change lines 89-90 from:
# Run the binaries at low priority?
# $NICE="nice -n 19 ";
to:
# Run the binaries at low priority?
$NICE="nice -n 19 ";
Save the changes to factMsieve.pl and proceed to the next step.
Step 3 - Polynomial Selection
The NFS algorithm uses a 3 phase method, the first being polynomial selection, then sieving, and finally linear algebra. Before factoring can begin, a polynomial must be selected. The easiest method for doing this is letting the GGNFS tools select one for you. With a couple of extra steps, msieve can also select a polynomial and will often reduce sieving time by 10-20% compared to the one selected by the ggnfs tools for numbers less than 140 digits. For instructions on using msieve, see the Using MSIEVE for Polynomial Selection in GNFS guide. Beginners should probably just use the GGNFS tools as explained next.
Change to your working directory (cd /home/jeff/ggnfs/example). In your working directory, create a text file called example.n and inside that file paste your number to factor, we will use the 121 digit example number and place "n: " in front so the file contains:
n: 8996941959382577683409613171454174240738275788293429353288678806601664747011544951714674576925430397444054300751795281737
Start the factoring process with the factMsieve.p perl script using this command from your working directory:
../factMsieve.pl example.n
This will call the pol51 tools to select a polynomial for the number in example.n. The output should look something like:
-> ___________________________________________________________
-> | This is the factMsieve.pl script for GGNFS. |
-> | This program is copyright 2004, Chris Monico, and subject|
-> | to the terms of the GNU General Public License version 2.|
-> |__________________________________________________________|
-> This is client 1 of 1
-> Using 2 threads
-> Working with NAME=example...
-> Error: Polynomial file example.poly does not exist!
-> Found n=899694195938257768340961317145417424073827578829342935328867880660166
4747011544951714674576925430397444054300751795281737.
-> Attempting to run polyselect...
-> Selected default polsel parameters for 121 digit level.
-> Selected default factorization parameters for 122 digit level.
-> Selected lattice siever: ../gnfs-lasieve4I13e.exe
-> Searching leading coefficients from 1 to 1000.
=> nice -n 19 "../pol51m0b.exe" -b example.polsel.machinename.2044 -v -v -p 4 -n 1.67E+018 -a 0 -A 1 > example.polsel.machinename.2044.log
For this example number, polynomial selection took approximately 2 hours, after which the perl script will automatically start the next steps for you.
Step 4 - Sieving and Linear Algebra
The final 2 phases of the NFS algorithm are taken care of for you by the factMsieve.pl perl script. After a polynomial has been selected, the script will automatically start the siever.
The output of the sieving phase will look something like this:
-> ___________________________________________________________
-> | This is the factMsieve.pl script for GGNFS. |
-> | This program is copyright 2004, Chris Monico, and subject|
-> | to the terms of the GNU General Public License version 2.|
-> |__________________________________________________________|
-> This is client 1 of 1
-> Using 1 threads
-> Working with NAME=example...
-> Selected default factorization parameters for 122 digit level.
-> Selected lattice siever: ../gnfs-lasieve4I13e
-> Creating param file to detect parameter changes...
-> Q0=2500000, QSTEP=60000.
-> makeJobFile(): q0=2500000, q1=2560000.
-> makeJobFile(): Adjusted to q0=2500000, q1=2560000.
-> Lattice sieving algebraic q-values from q=2500000 to 2560000.
=> "../gnfs-lasieve4I13e" -k -o spairs.out -v -n0 -a example.job
FBsize 182730+0 (deg 5), 348512+0 (deg 1)
total yield: 181, q=2500049 (0.03459 sec/rel)
If you need to stop your job before it is complete, press CTRL-C and wait a minute for the siever to end gracefully. This should allow you to restart where you left off by running a similar command as above from your working directory. This time instead of passing example.n on the command line you pass example.poly. To be safe, it is a good idea to back up your files in ggnfs/example before you re-start, just in case. To continue factoring from where you left off, run:
../factMsieve.pl example.poly
After reaching an estimated minimum number of relations, the script will run msieve to see if enough relations have been collection to perform the linear algebra phase. If not, sieving will automatically continue. At some point, enough relations will be available and the script will automatically call msieve to perform the final linear algebra steps. Once this is complete, the factors will be shown. For our example number, roughly 8.5 million relations were needed and took around 4 days of sieving on 1 processor of a Pentium4 3 GHz machine. Make sure you have enough free disk space as the relations take up a lot of room; the 8.5 millions relations and intermediate files used 1.2 GB of space. The msieve program was then automatically called to do the linear algebra which took a couple of hours and the results will look something like this:
<some data snipped>
.
.
commencing square root phase
reading relations for dependency 1
read 353299 cycles
cycles contain 1407657 unique relations
read 1407657 relations
multiplying 1151656 relations
multiply complete, coefficients have about 51.48 million bits
initial square root is modulo 24600791
reading relations for dependency 2
read 352893 cycles
cycles contain 1406530 unique relations
read 1406530 relations
multiplying 1149570 relations
multiply complete, coefficients have about 51.38 million bits
initial square root is modulo 23829469
prp58 factor: 7113268608388826628041175633889105572982840043845203074777
prp64 factor: 1264811221773952923237987117254409784246941529158530073219882481
elapsed time 00:29:35
-> Computing time scale for this machine...
sumName = g121-C121_104_57.txt
-> Factorization summary written to g121-example.txt.
As you can see from the output, the example number had 2 probable prime (prp) factors, one 58 digits (7113268608388826628041175633889105572982840043845203074777) and the other 64 digits (1264811221773952923237987117254409784246941529158530073219882481). You can verify your results by multiplying the two factors together and confirm they equal the original number you were trying to factor.
Step 5 - Enjoy the Factors
Congrats you have just finished factoring your integer and now you are done. Enjoy. Remember that factoring larger numbers will take longer to select a good polynomial, sieve, and require more time and memory for the linear algebra stages. Factoring a 155 digit number for example using GNFS will take months on a quad-core PC.
SNFS Factoring - Special Number Field Sieve
You can also use GGNFS and MSIEVE to factor numbers using the Special Number Field Sieve (SNFS) which is beyond the scope of this guide. Details about SNFS polynomial selection are available. Several programs are available to generate SNFS polynomials for some special numbers, such as Homogenous Cunninghams, Cunninghams, and XYYX that you might need to compile yourself. Create the polynomial file for the SNFS number you want to factor, and instead of using "type: gnfs" you need to use "type: snfs". The rest of the instructions for factoring should be similar for SNFS.
It was recently announced that Benjamin Moody has factored an RSA-512 bit key in 73 hours using only public software and his desktop computer. The first RSA-512 factorization in 1999 required the equivalent of 8,400 MIPS years over an elapsed time of about 7 months. The announcement was made all the more intriguing in that it came from a mailing list associated with a user forum for Texas Instruments calculators.
The public key in question is used to verify signed OS binaries for the TI 83 Plus and the factorization means that
… any operating system can be cryptographically signed in a manner identical to that of the original TI-OS. Third party operating systems can thus be loaded on any 83+ calculators without the use of any extra software (that was mentioned in recent news). Complete programming freedom has finally been achieved on the TI-83 Plus!
The original post from Moody was not very informative, but the subsequent Q & A thread drew out more details. Moody used public source factoring software on a dual-core Athlon64 at 1900 MHz. Just under 5 gigabytes of disk was required and about 2.5 gigabytes of RAM for the sieving process. The final computation involved finding the null space of a 5.4 million x 5.4 million matrix.
Most security people would rightly claim that RSA-512 is known to be provide little security as a keylength, however this does not mean that 512-bit public keys are not in use today by companies other than Texas Instruments. By the way, someone is offering an RSA 512 factoring service with a “price indication” of $5000.
