Andreas Dittes

From: “Jens Franke”
Date: Fri, 04 Nov 2005 16:53:08 +0100

We have factored RSA640 by GNFS. The factors are

16347336458092538484431338838650908598417836700330\
92312181110852389333100104508151212118167511579

and

19008712816648221131268515739354139754718967899685\
15493666638539088027103802104498957191261465571

We did lattice sieving for most special q between 28e7 and 77e7
using factor base bounds of 28e7 on the algebraic side and 15e7 on
the rational side. The bounds for large primes were 2^34. This produced
166e7 relations. After removing duplicates 143e7 relations
remained. A filter job produced a matrix with 36e6 rows and columns,
having 74e8 non-zero entries. This was solved by Block-Lanczos.

Sieving has been done on 80 2.2 GHz Opteron CPUs and took 3 months.
The matrix step was performed on a cluster of 80 2.2 GHz Opterons
connected via a Gigabit network and took about 1.5 months.

Calendar time for the factorization (without polynomial selection)
was 5 months.

More details will be given later.

F. Bahr, M. Boehm, J. Franke, T. Kleinjung

(Originaltext)

Das ganze wurde im Zusammenhang mit der RSA-Challenge der RSA-Security vollzogen. Aufgabe war es eben, eine Zahl mit 193 Dezimalstellen in ihre beiden Primfaktoren zu zerlegen. Geschafft hat die Forschergruppe dies nach 5 Monaten Rechenzeit von 80 2,2Ghz Prozessoren eines Opteron Clusters mit der General Number Field Sieve (GNFS)-Methode.

GGNFS is a rudimentary implementation of the General Number Field Sieve (GNFS) for factoring integers. I wrote it because I was dismayed that there is no such source code widely available. It is coming along nicely, and some people have used it to factor some interesting numbers. It has been used on SNFS numbers upto 157 digits and general numbers upto 120. It is not perfect yet, and it is almost entirely documentation-free, but it is available.

Heise erläutert ausserdem, welche Schwierigkeiten bei der Faktorzerlegung auftreten können und warum die Zukunft wohl in dem abgeänderten mathematischen Berechnungsverfahren der Elliptic-Curve-Cryptography (ECC) liegt. Ein Post dazu folgt eventuell später noch…
(BTW @Heise: Cryptography, nicht Crytography…)