Using MSIEVE for Polynomial Selection in GNFS

by Jeff Gilchrist
Jeff's E-mail Address

Last Updated:  January 12, 2010

This page is part of the Beginners Guide to NFS factoring using GGNFS and MSIEVE with the factmsieve.pl perl script guide.  It explains an alternate method of selecting a polynomial for GNFS using the msieve tool.   For the rest of the steps, please refer to the main guide page linked above.


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 using MSIEVE to select one for you.  

Change to your working directory (cd /home/jeff/ggnfs/example).  In your working directory, create a text file called worktodo.ini and inside that file paste your number to factor, we will use the 121 digit example number:
8996941959382577683409613171454174240738275788293429353288678806601664747011544951714674576925430397444054300751795281737

Run msieve using the polynomial selection command:
../msieve -p -v -np

This will cause msieve to select a polynomial (-np) for the number in worktodo.ini in verbose mode (-v) using low priority (-p) so it does not interfere with other programs on your system.  The output should look something like:

Msieve v. 1.39
Tue Feb  3 21:16:36 2009
random seeds: eb9a316c f26a5cd2
factoring 8996941959382577683409613171454174240738275788293429353288678806601664747011544951714674576925430397444054300751795281737 (121 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (121-digit input)
commencing number field sieve polynomial selection
time limit set to 4.71 hours
searching leading coefficients from 7862 to 37203
deadline: 100 seconds per coefficient
.
.
<5 hours of data snipped>
.
.
polynomial selection complete
R0: -229797237856764019652840
R1:  10962976683487
A0:  29092372201085715141523395410151
A1:  975426616405837620446202
A2: -628095578103273795520
A3: -752822784678274
A4:  2568297161
A5:  14040
skew 279167.28, size 9.381323e-13, alpha -7.594642, combined = 1.179509e-11
elapsed time 05:33:58

With our example number, msieve ran for almost 5 hours to try and find the best polynomial for the factoring job in that time limit.  Once complete, a file msieve.fb will contain the best results.  In order for this polynomial to be used with GGNFS, the data needs to be formatted slightly differently.  Luckily tmorrow created a convertpoly.sh script you can download and save in your ggnfs directory (/home/jeff/ggnfs).  

Run the script as follows from your working directory:
../convertpoly.sh example

The script will copy the file msieve.fb to example.poly and convert the data to the proper formatting.  The file msieve.fb will look something like this:

N 8996941959382577683409613171454174240738275788293429353288678806601664747011544951714674576925430397444054300751795281737
SKEW 279167.28
R0 -229797237856764019652840
R1  10962976683487
A0  29092372201085715141523395410151
A1  975426616405837620446202
A2 -628095578103273795520
A3 -752822784678274
A4  2568297161
A5  14040

The new example.poly file will have changed "N" to "n", the "SKEW" to "skew", "R" to "Y", "A" to "c", and add ":" after all the entries.  It will also add "type: gnfs" so that example.poly looks like this:

n: 8996941959382577683409613171454174240738275788293429353288678806601664747011544951714674576925430397444054300751795281737
Y0: -229797237856764019652840
Y1:  10962976683487
c0:  29092372201085715141523395410151
c1:  975426616405837620446202
c2: -628095578103273795520
c3: -752822784678274
c4:  2568297161
c5:  14040
skew: 279167.28
type: gnfs


Step 4 - Sieving and Linear Algebra

The final 2 phases of the NFS algorithm are taken care of for you in the factMsieve.pl perl script.  Now that you have created your polynomial file, you can start the remaining factoring process using this command from your working directory:
../factMsieve.pl example.poly

Return to the main Beginners Guide to NFS factoring using GGNFS and MSIEVE with the factmsieve.pl perl script to see the remaining steps in the factoring process.

  • This web page is maintained by Jeff Gilchrist, Copyright (C) 2010.
  • This web page best viewed using a resolution of 800 x 600 or higher.