Date: Tue, 1 Apr 2003 14:05:10 +0200
From: Jens Franke
Subject: RSA-160
We have factored RSA160 by gnfs. The prime factors are:
p=45427892858481394071686190649738831\
656137145778469793250959984709250004157335359
q=47388090603832016196633832303788951\
973268922921040957944741354648812028493909367
The prime factors of p-1 are 2 37 41 43 61 541 13951723
7268655850686072522262146377121494569334513 and
104046987091804241291 .
The prime factors of p+1 are 2^8 5 3 3 13 98104939 25019146414499357
3837489523921 and 128817892337379461014736577801538358843 .
The prime factors of q-1 are 2 9973 165833
11356507337369007109137638293561
369456908150299181 and 3414553020359960488907 .
The prime factors of q+1 are 2^3 3 3 13 82811 31715129
7996901997270235141
and
2410555174495514785843863322472689176530759197.
The computations for the factorization of RSA160 took place at the
Bundesamt fur Sicherheit in der Informationstechnik (BSI) in Bonn.
Lattice sieving took place between Dec. 20, 2002 and Jan. 6,
2003, using 32 R12000 and 72 Alpha EV67. The total yield of
lattice sieving was 323778082.
Uniqueness checks reduced the number of sieve reports to
289145711. After
the filtering step, we obtained an almost square matrix of
size with 5037191
columns. Block Lanczos for this matrix took 148 hours on 25
R12000 CPUs. The
square root steps took an average of 1.5 hours on a 1.8 GHz
P4 CPU, giving the
factors of RSA160 after processing the 6-th lanczos solution.
F. Bahr J. Franke T. Kleinjung M. Lochter M. Bohm