>  Recent Factors, below 

See new Perl script, below:

Jason Papadopoulos wrote the factoring program Msieve which started life a few years ago using the Quadratic Sieve method.  It can now easily handle numbers up to 100 digits.

The current version is Msieve 1.43 and is available either as a Linux C++ source code package in a tar.gz file (400 KB) or as a Windows executable (about 600 KB).

The more advanced Number Field Sieve method is now being added into the program.  Both methods involve sieving followed by the solution of a large linear matrix.  The code has become so good that for very large numbers, the NFS sieving part can be done by GGNFS (see below), but the linear algebra, too large for GGNFS, can be handled by Msieve.

I recently came across a 183 digit composite number that caused a memory allocation error when GGNFS came to load the matrix into memory, saying that it wanted 721 MB.  The machine actually had 2 GB, so previous memory requests had probably fragmented the memory, causing the crash.

Msieve, however, loaded the GGNFS-format data and solved the 779,725 × 779,973 matrix, not only using less memory (250 MB vs. 721 MB), but in a shorter time (05:11:32 hrs compared to possibly 24 hrs for such a large number).  The prime factors turned out to be p48 • p48 • p87 showing that very large composites don't always have very large prime factors.

Here are the comparative matrix-solution times for a 166 digit number (with SNFS difficulty 167 digits) that succeeded using both GGNFS and Msieve:

• For GGNFS:

Initial matrix: 433802 x 491774 with sparse part having weight 54393195.
Pruned matrix : 412924 x 415157 with weight 43131647.
...
Matrix solve time: 5.82 hours.
Total square root time: 0.15 hours, sqrts: 1.

• For Msieve:

matrix is 543812 x 544059 with weight 35189856 (avg 64.68/col)
...
commencing square root phase
reading relations for dependency 1
...
elapsed time 02:03:21

The parameter files for Msieve are slightly different from the GGNFS format and need conversion (only a matter of a few seconds) before running Msieve.  The makems Perl script to automate this process was posted to the XYYXF Yahoo! Group as message number 1185 in October, 2007.  See below for the script:

Most of the factors listed below were found using the Special Number Field Sieve method.  In the past, this has been only available to mathematical researchers at Universities with super-computers like the CWI (Centrum voor Wiskunde en Informatica, or the Center for Mathematics and Computer Science) in the Netherlands.

See a very interesting CWI report produced by Dr. Herman te Riele which covers several recent record factorisations on the topic: Factoring large integers with the Number Field Sieve.

In 2005, an open-source C program called GGNFS was written by Chris Monico of the Texas Tech University to run on fast PCs with 1 or 2 GB of memory. The software is provided as a set of source modules along with a Makefile script to install and run on Linux. The program itself is then run via a Perl script which executes the various phases of the calculation (sieving, processing, matrix inversion and finally the sqrt phase).

It is by no means a set-and-forget method since it is still in development and being improved by contributions from many people around the world. There are still bugs present and when it crashes, it takes some ingenuity to resume the calculations without too much loss of data - a typical run generating several gigabytes.

For answers to typical questions, go to the GGNFS Yahoo! Group.

The software can also be run on Windows based PCs under a program called Cygwin.  This gives a command line interface to a simulated Linux shell which allows the factoring program to run.  Quoting from the Cygwin web-site:

Cygwin is a Linux-like environment for Windows.  It consists of two parts:

• A DLL (cygwin1.dll) which acts as a Linux API emulation layer providing substantial Linux API functionality.
• A collection of tools which provide Linux look and feel.

>  Top of page  ::  Bottom of page