• Types of Numbers
There are several different types of numbers represented in these tables.
There are numbers of the form a × bn ± c or xy + yx.
Others arise from arithmetic series like the Wolstenholme numbers.
The simplest example is the numerator of a sum of reciprocals.
For example, 1/1 + 1/2 + 1/3 + 1/4 + 1/5 gives 137/60, and so Wol(5) = 137, a prime.
Substituting powers of these reciprocals produces similar numbers, Wol2(n), Wol3(n) etc. using squares or cubes respectively.
In general, we have: Wolk(n) = Σ 1/jk summing from j=1 to n.
For example, 1/12 + 1/22 + 1/32 + 1/42 + 1/52 gives 5269/3600, and so Wol2(5) = 5269 = 11 × 479.
Extensive tables of these and many other types of numbers are collected on the
website of Hisanori Mishima at his modestly entitled WIFC (World Integer Factorization Center) :-).
See new Perl script, below:
Jason Papadopoulos wrote the
Msieve which started life a few years ago using the
Quadratic Sieve method. It can now easily handle numbers up to
200 digits by a single machine.
The current version is
Msieve v. 1.50
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
but the linear algebra, too large for GGNFS, can be handled by Msieve.
In fact, it has been used to tackle a record 180-digit General number
and also a Special number of 277-digits.
A General number of 190 digits has just been factored on Nov 8, 2010.
-- See after the 180 digit report, below.
The 180-digit number was the residual composite left from 5421-1
which factorises as:
|p37||=||6226633359276226469107090691434236881 • C180
The worldwide cooperative effort was run from about July 2008 to
November 2008 and involved many dozens of researchers with hundreds
of computers. Go to the
for the full story. The final result from all this effort was a
p66 • p115 factorisation.
The 190-digit number factored using Msieve was the RSA-190 Challenge
"The job was done by I.Popovyan from MSU, Russia and A. Timofeev from
CWI, Netherlands and took a few months of a pure computer time on various
parallel systems in both MSU and CWI".
For the full report, see the
"We are happy to report that after almost a half a year on November
8th, 2010 we finally got the factorization of the RSA-190 as follows:"
The Special number of 277-digits was 12256+1 which is a
Generalised Fermat Number - Fermat Numbers are of the form
22n+1. There were three known factors (with 7, 12 and 31
digits), so there remained a C228 to be factored.
The SNFS difficulty was, however, still 277.
|p31||=||5763919006323142831065059613697 • C228
This enormous factorisation was carried out by the researchers Thomas Womack
and Bruce Dodson (collectively fivemack on the
It was conducted over several months in 2009, ending
on 17 August with a p96 • p132 factorisation.
NEWThe factorization of the number 21061 - 1 of 320 decimal digits was completed on August 4, 2012 by Greg Childers.
See the paper at http://eprint.iacr.org/2012/444.pdf.
Factorization of a 1061-bit number by the Special
Number Field Sieve
California State University Fullerton
Fullerton, CA 92831
August 4, 2012
It was a World-wide effort from over 1,000 individuals contributing computing time to the NFS@Home project.
Quoting from the paper:
Using the SNFS, the complete factorization of the Mersenne number, 21061 - 1, has been
determined. Prior this (sic) this effort, this number had no known factors. Although easier than
the factorization of RSA-768, this represents a new largest factorization using SNFS, and
the largest factorization to date using publicly available software.
The number 21061 - 1 is the product of 143-digit and 177-digit prime numbers, p143 and p177, where
• Msieve / GGNFS Comparison
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
Here are the comparative matrix-solution times for a 166 digit number
(with SNFS difficulty 167 digits) that succeeded using both GGNFS
• 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
• Msieve Perl Script
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
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
(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
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 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
A collection of tools which provide Linux look and feel.
• Recent Factors
|Nov 25, 2012|
|65 • 10197 + 7 ||c164||p43:
||6169711486855697338854111302960147268456581 • |
|65 • 10195 + 7 ||c183||p91:
||5754783689304120658127798005794393634928558512673865943969645138492069142273252536693493353 • |
|Nov 18, 2012|
|14 • 10200 + 31 ||c159||p43:
||2447154381250819573149562281510462227670001 • |
|Nov 17, 2012|
|83 • 10199 + 61 ||c172||p58:
||4132125803952506141973560689972426772329394536941635736871 • |
|Nov 15, 2012|
|83 • 10200 + 61 ||c165||p60:
||302275707150262798231021058269653289863123489228427630182619 • |
|Nov 13, 2012|
|58 • 10200 - 31 ||c165||p45:
||646432074643177003283488166543485882439404087 • |
|Nov 11, 2012|
|5 • 10200 - 9 ||c166||p49:
||2583225704384937328000587461759654291646576490909 • |
|Nov 10, 2012|
|44 • 10204 - 71 ||c161||p52:
||1270245249570419236930166222029399170416319922170701 • |
|Nov 7, 2012|
|44 • 10202 - 71 ||c171||p65:
||75878463711207153504808610329401307552197609675535739597097130019 • |
|Nov 5, 2012|
|44 • 10201 - 71 ||c175||p78:
||179743823691321096083250716842479114494187192509107805237247659865791490401737 • |
|Nov 3, 2012|
|44 • 10200 - 71 ||c166||p58:
||2365645867052241385948677925915206162679514062779961067629 • |
|Nov 2, 2012|
|38 • 10202 + 43 ||c156||p47:
||12177595753171528456869788185542291304855088489 • |
> Top of page