Integer factorization records
Encyclopedia
Integer factorization
is the process of determining which prime number
s divide a given positive integer
. Doing this quickly has applications in cryptography
. The difficulty depends on both the size and form of the number and its prime factor
s; it is currently very difficult to factorize large semiprimes (and, indeed, most numbers which have no small factors).
, with relations contributed by about 600 people from all over the Internet, and the final stages of the calculation performed on a MasPar
supercomputer at Bell Labs.
Between January and August 1999, RSA-155, a challenge number prepared by the RSA company, was factorised using GNFS with relations again contributed by a large group, and the final stages of the calculation performed in just over nine days on the Cray
C916
supercomputer at the SARA Amsterdam Academic Computer Center.
In January 2002, Franke et al. announced the factorisation of a 158-digit cofactor of 2953+1, using a couple of months on about 25 PCs at the University of Bonn
, with the final stages done using a cluster of six Pentium-III PCs.
In April 2003, the same team factored RSA-160 using about a hundred CPUs at BSI, with the final stages of the calculation done using 25 processors of an SGI
Origin
supercomputer.
The 174-digit RSA-576 was factored by Franke, Kleinjung and members of the NFSNET collaboration in December 2003, using resources at BSI and the University of Bonn; soon afterwards, Aoki, Kida, Shimoyama, Sonoda and Ueda announced that they had factored a 164-digit cofactor of 21826+1.
A 176-digit cofactor of 11281+1 was factored by Aoki, Kida, Shimoyama and Ueda between February and May 2005 using machines at NTT
and Rikkyo University
in Japan.
The RSA-200 challenge number was factored by Franke, Kleinjung et al. between December 2003 and May 2005, using a cluster of 80 Opteron processors at BSI in Germany; the announcement was made on 9 May 2005. They later (November 2005) factored the slightly smaller RSA-640 challenge number.
On December 12, 2009, a team including researchers from the CWI, the EPFL, INRIA and NTT in addition to the authors of the previous record factored RSA-768, a 232-digit semiprime. They used the equivalent of almost 2000
years of computing on a single core 2.2 GHz AMD
Opteron
.
.
2773 + 1, of 774 bits (233 digits), was factored between April and November 2000 by 'The Cabal', with the matrix step done over 250 hours on the Cray also used for RSA-155.
2809 − 1, of 809 bits (244 digits), had its factorisation announced at the start of January 2003. Sieving was done at the CWI, at the Scientific Computing Institute and the Pure Mathematics Department at Bonn University, and using private resources of J. Franke, T. Kleinjung and the family of F. Bahr. The linear algebra step was done by P. Montgomery at SARA in Amsterdam.
6353 − 1, of 911 bits (275 digits), was factored by Aoki, Kida, Shimoyama and Ueda between September 2005 and January 2006 using SNFS
.
21039 − 1, of 1039 bits (313 digits) (though a factor of 23 bits was already known) was factored between September 2006 and May 2007 by a group including K. Aoki, J. Franke, T. Kleinjung, A. K. Lenstra and D. A. Osvik, using computers at NTT
, EPFL
and the University of Bonn
.
In 2009, Benjamin Moody factored a 512-bit RSA key used to sign the TI-83
graphing calculator using software found on the internet; this eventually led to the Texas Instruments signing key controversy
.
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
is the process of determining which prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s divide a given positive integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
. Doing this quickly has applications in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. The difficulty depends on both the size and form of the number and its prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
s; it is currently very difficult to factorize large semiprimes (and, indeed, most numbers which have no small factors).
Numbers of a general form
The first very large distributed factorisation was RSA129, a challenge number described in the Scientific American article of 1977 which first popularised the RSA cryptosystem. It was factorised between September 1993 and April 1994, using MPQSQuadratic sieve
The quadratic sieve algorithm is a modern integer factorization algorithm and, in practice, the second fastest method known . It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve...
, with relations contributed by about 600 people from all over the Internet, and the final stages of the calculation performed on a MasPar
MasPar
MasPar Computer Corporation was a minisupercomputer vendor that was founded in 1987 by Jeff Kalb. The company was based in Sunnyvale, California....
supercomputer at Bell Labs.
Between January and August 1999, RSA-155, a challenge number prepared by the RSA company, was factorised using GNFS with relations again contributed by a large group, and the final stages of the calculation performed in just over nine days on the Cray
Cray
Cray Inc. is an American supercomputer manufacturer based in Seattle, Washington. The company's predecessor, Cray Research, Inc. , was founded in 1972 by computer designer Seymour Cray. Seymour Cray went on to form the spin-off Cray Computer Corporation , in 1989, which went bankrupt in 1995,...
C916
Cray C90
The Cray C90 series was a vector processor supercomputer launched by Cray Research in 1991. The C90 was a development of the Cray Y-MP architecture. Compared to the Y-MP, the C90 processor had a dual vector pipeline and a faster 4.1 ns clock cycle , which together gave three times the...
supercomputer at the SARA Amsterdam Academic Computer Center.
In January 2002, Franke et al. announced the factorisation of a 158-digit cofactor of 2953+1, using a couple of months on about 25 PCs at the University of Bonn
University of Bonn
The University of Bonn is a public research university located in Bonn, Germany. Founded in its present form in 1818, as the linear successor of earlier academic institutions, the University of Bonn is today one of the leading universities in Germany. The University of Bonn offers a large number...
, with the final stages done using a cluster of six Pentium-III PCs.
In April 2003, the same team factored RSA-160 using about a hundred CPUs at BSI, with the final stages of the calculation done using 25 processors of an SGI
Silicon Graphics
Silicon Graphics, Inc. was a manufacturer of high-performance computing solutions, including computer hardware and software, founded in 1981 by Jim Clark...
Origin
SGI Origin 200
The SGI Origin 200, code named Speedo, is an entry-level server computer developed and manufactured by SGI, introduced in October 1996 to accompany their mid-range and high-end Origin 2000. It is based on the same architecture as the Origin 2000 but has an unrelated hardware implementation...
supercomputer.
The 174-digit RSA-576 was factored by Franke, Kleinjung and members of the NFSNET collaboration in December 2003, using resources at BSI and the University of Bonn; soon afterwards, Aoki, Kida, Shimoyama, Sonoda and Ueda announced that they had factored a 164-digit cofactor of 21826+1.
A 176-digit cofactor of 11281+1 was factored by Aoki, Kida, Shimoyama and Ueda between February and May 2005 using machines at NTT
Nippon Telegraph and Telephone
, commonly known as NTT, is a Japanese telecommunications company headquartered in Tokyo, Japan. Ranked the 31st in Fortune Global 500, NTT is the largest telecommunications company in Asia, and the second-largest in the world in terms of revenue....
and Rikkyo University
Rikkyo University
, also known as Saint Paul's University, is a private university, based on Christian precepts, in Ikebukuro, Tokyo. There is a suburban campus in Niiza in nearby Saitama.It is known for its liberal climate symbolized by the motto -History:...
in Japan.
The RSA-200 challenge number was factored by Franke, Kleinjung et al. between December 2003 and May 2005, using a cluster of 80 Opteron processors at BSI in Germany; the announcement was made on 9 May 2005. They later (November 2005) factored the slightly smaller RSA-640 challenge number.
On December 12, 2009, a team including researchers from the CWI, the EPFL, INRIA and NTT in addition to the authors of the previous record factored RSA-768, a 232-digit semiprime. They used the equivalent of almost 2000
years of computing on a single core 2.2 GHz AMD
Advanced Micro Devices
Advanced Micro Devices, Inc. or AMD is an American multinational semiconductor company based in Sunnyvale, California, that develops computer processors and related technologies for commercial and consumer markets...
Opteron
Opteron
Opteron is AMD's x86 server and workstation processor line, and was the first processor which supported the AMD64 instruction set architecture . It was released on April 22, 2003 with the SledgeHammer core and was intended to compete in the server and workstation markets, particularly in the same...
.
Numbers of a special form
12151 − 1, of 542 bits (163 digits), was factored between April and July 1993 by a team at CWI and Oregon State UniversityOregon State University
Oregon State University is a coeducational, public research university located in Corvallis, Oregon, United States. The university offers undergraduate, graduate and doctoral degrees and a multitude of research opportunities. There are more than 200 academic degree programs offered through the...
.
2773 + 1, of 774 bits (233 digits), was factored between April and November 2000 by 'The Cabal', with the matrix step done over 250 hours on the Cray also used for RSA-155.
2809 − 1, of 809 bits (244 digits), had its factorisation announced at the start of January 2003. Sieving was done at the CWI, at the Scientific Computing Institute and the Pure Mathematics Department at Bonn University, and using private resources of J. Franke, T. Kleinjung and the family of F. Bahr. The linear algebra step was done by P. Montgomery at SARA in Amsterdam.
6353 − 1, of 911 bits (275 digits), was factored by Aoki, Kida, Shimoyama and Ueda between September 2005 and January 2006 using SNFS
Special number field sieve
In number theory, a branch of mathematics, the special number field sieve is a special-purpose integer factorization algorithm. The general number field sieve was derived from it....
.
21039 − 1, of 1039 bits (313 digits) (though a factor of 23 bits was already known) was factored between September 2006 and May 2007 by a group including K. Aoki, J. Franke, T. Kleinjung, A. K. Lenstra and D. A. Osvik, using computers at NTT
Nippon Telegraph and Telephone
, commonly known as NTT, is a Japanese telecommunications company headquartered in Tokyo, Japan. Ranked the 31st in Fortune Global 500, NTT is the largest telecommunications company in Asia, and the second-largest in the world in terms of revenue....
, EPFL
École polytechnique fédérale de Lausanne
The École polytechnique fédérale de Lausanne is one of the two Swiss Federal Institutes of Technology and is located in Lausanne, Switzerland.The school was founded by the Swiss Federal Government with the stated mission to:...
and the University of Bonn
University of Bonn
The University of Bonn is a public research university located in Bonn, Germany. Founded in its present form in 1818, as the linear successor of earlier academic institutions, the University of Bonn is today one of the leading universities in Germany. The University of Bonn offers a large number...
.
Comparison to efforts by individuals
As of the end of 2007, thanks to the constant decline in memory prices, the ready availability of multi-core 64-bit computers, and the availability of the Bonn group (now mostly at Nancy)'s efficient sieving code via ggnfs and robust open-source software such as msieve for the finishing stages, special-form numbers of up to 750 bits and general-form numbers of up to about 520 bits can be factored in a few months on a few PCs by a single person without any special mathematical experience. These bounds increase to about 950 and 600 if it were possible to secure the collaboration of a few dozen PCs; currently the amount of memory and the CPU power of a single machine for the finishing stage are equal barriers to progress.In 2009, Benjamin Moody factored a 512-bit RSA key used to sign the TI-83
TI-83 series
The TI-83 series of graphing calculators is manufactured by Texas Instruments.The original TI-83 is itself an upgraded version of the TI-82. Released in 1996, it is one of the most used graphing calculators for students...
graphing calculator using software found on the internet; this eventually led to the Texas Instruments signing key controversy
Texas Instruments signing key controversy
The Texas Instruments signing key controversy refers to the controversy which resulted from Texas Instruments' response to a project to factorize the 512-bit RSA cryptographic keys needed to write custom firmware to TI devices.-Project:...
.