Cryptography Watch

A new paper on polynomial selection in the General Number Field Sieve has been published[1]. The new method involves the creation of nonmonic linears. It is not expected to greatly increase the yield over Murphy’s method [2]. This code has been implemented in the pol5 code of Monico’s GGNFS.

[1] Kleinjund, T., On Polynomial Selection for the General Number Field Sieve, Mathematics of Computation, 75(256), 2006, pp 2037-2047.

Abstract:
The general number field sieve (GNFS) is the asymptotically fastest algorithm for factoring large integers. Its runtime depends on a good choice of a polynomial pair. In this article we present an improvement of the polynomial selection method of Montgomery and Murphy which has been used in recent GNFS records.

[2] Murphy, B. A., Brent, R. P. On Quadratic Polynomials for the Number Field Sieve, Computing Theory 98, ACSC 20(3), 1998, pp 199-215.

The number RSA-640 of the RSA Factoring Challenge has been factored by Bahr, F.; Boehm, M.; Franke, J. and Kleinjung, T. of the German Federal Agency for Information Technology Security (BSI). The factorization took five months on 80 2.2 GHz AMD Opteron CPUs using the General Number Field Sieve.

The result was:

RSA-640 = 16347336458092538484431338838650908598417836700330923121
81110852389333100104508151212118167511579
* 19008712816648221131268515739354139754718967899685154936
66638539088027103802104498957191261465571

Dr. Christopher Monico, an Assistant Professor in the Department of Mathematics and Statistics at Texas Tech University, has released the GPL’d source code to an implementation of the General Number Field Sieve. The code is only able to handle semi-primes of about 120 digits at this time. However, it is possible that this code will gain a good deal of attention and see the kind of improvement need to make it a threat to smaller PGP keys over the next few years. The primary issues with the code at this time are memory management and multi/distributed processing capabilities.

GGNFS Homepage

GGNFS SourceForge Development Page

RSA-576 (174 decimal digits) has been factored using the General Number Field Sieve by Franke, J. et. al.

The result was:

RSA-576 = 3980750864240649373971255005503864911990643623
42526708406385189575946388957261768583317
* 4727721461074353025362230719730482246329146953020971164
59852171130520711256363590397527

Researchers have demonstrated Shor’s Quantum Factoring Algorithm experimentally on a 4bit number[1]. Researchers were able to use the algorithm to determine the factors of the number 15, 3 and 5.

[1] Vandersypen, L. M. K., Steffen, M., Breyta, G., Yannoni, C. S., Sherwood, M. H., Chuang, I. L. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance, Nature 414, 883-887 (2001).

Abstract
The number of steps any classical computer requires in order to find
the prime factors of an l-digit integer N increases exponentially with l, at
least using algorithms known at present. Factoring large integers is therefore
conjectured to be intractable classically, an observation underlying the security
of widely used cryptographic codes. Quantum computers, however, could factor
integers in only polynomial time, using Shor’s quantum factoring algorithm.
Although important for the study of quantum computers, experimental
demonstration of this algorithm has proved elusive. Here we report an
implementation of the simplest instance of Shor’s algorithm: factorization
of N = 15 (whose prime factors are 3 and 5). We use seven spin-1/2
nuclei in a molecule as quantum bits, which can be manipulated with
room temperature liquid-state nuclear magnetic resonance techniques.
This method of using nuclei to store quantum information is in principle
scalable to systems containing many quantum bits, but such scalability
is not implied by the present work. The significance of our work lies in
the demonstration of experimental and theoretical techniques for precise
control and modeling of complex quantum computers. In particular, we
present a simple, parameter-free but predictive model of decoherence
effects in our system.

The number RSA-140 of the RSA Factoring Challenge {W} has been factored by Herman J. J. te Riele {W}, et. al.

The factorization is:

RSA-140 = 3398717423028438554530123627613875835633986495969597423490929302771479
* 6264200187401285096151654948264442219302037178623509019111660653946049

The RSA-130 Number of the RSA Factoring Challenge has been factored by Lenstra, et. al.

RSA-130 has the factorization:

RSA-130 = 39685999459597454290161126162883786067576449112810064832555157243
* 45534498646735972188403686897274408864356301263205069600999044599

Peter Shor {W} has published a paper which describes a polynomial time factorization algorithm[1].

Shor, Peter W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SICOMP Volume 26 Issue 5 pp. 1484-1509, 1997.*

Abstract:

A digital computer is generally believed to be an efficient universal computing
device; that is, it is believed able to simulate any physical computing device with an
increase in computation time of at most a polynomial factor. This may not be true
when quantum mechanics is taken into consideration. This paper considers factoring
integers and finding discrete logarithms, two problems which are generally thought
to be hard on a classical computer and have been used as the basis of several
proposed cryptosystems. Efficient randomized algorithms are given for these two
problems on a hypothetical quantum computer. These algorithms take a number
of steps polynomial in the input size, e.g., the number of digits of the integer to
be factored.

* Reference updated to reflect revised draft.

The semi-prime RSA-129, of the RSA Factoring Challenge, has been factored by Lenstra, A., et. al. using a distributed computing approach involving roughly 600 computers.  The factorization was done using the Multiple Polynomial Quadratic Sieve (MPQS).

The result was:

RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577
* 32769132993266709549961988190834461413177642967992942539798288533

The number RSA-120 of the RSA Factoring Challenge {W} has been factored[1] by Derek Atkins, Michael Graff, Arjen K. Lenstra {W}, and Paul Leyland {W}.

The factorization is:

RSA-120 = 327414555693498015751146303749141488063642403240171463406883
* 693342667110830181197325401899700641361965863127336680673013

The computation took approximately three months.

[1] Denny, T., Dodson, B., Lenstra, A.K., Manasse, M.S. (1994), On the Factorization of RSA-120, Lecture Notes in Computer Science 773, Springer-Verlag, 1994, pp 166-174.