From:   matyukhin_dv@GOV.RU
Subject: Discrete logarithm in GF(p) --- 135 digits
Date: December 22, 2006 14:37:11 GMT+01:00
To:   NMBRTHRY@LISTSERV.NODAK.EDU
Reply-To:   matyukhin_dv@GOV.RU


We are very pleased to announce that we have computed discrete
logarithm modulo a 135 digits (448 bits) prime. As far as we know,
this is a new record for the general discrete logarithm problem.
Precisely, we took a strong prime

p = \lfloor 2^{446} \pi \rfloor+63384 =
5708577991479139431420732981594532907473762955504519051138653759118659185880
22945237020702500203437615419679961659928369778961422486479

and a generator of the multiplicative group mod p

g = 7

and computed

11 =
g^26380941544253268435779383277762670448370011005096163124033661054514364572
303487227503001638396257384118164938889215403106849600742712.

This result was obtained using original variant of the number field
sieve that may be viewed as a combination of Schirokauer's, Weber's
and Joux&Lercier's ideas with an original approach to the choice of
polynomials and structured Gauss elimination.

The number fields were defined by

X^3+9X^2-X+3

and

263709209259700609070351642896762069756131120X^2
-130043864502764389781961449585369078203763779X
-452577888141205980600106372309912676562565249.

The factor bases bounds were 11116891 and 37392614 respectively.

We used line sieving without large primes. After 24300 MIPS-years we
obtained 2541033 linear equations with 2739345 unknowns and 57250340
non zero entries.

We first applied our version of structured Gaussian elimination to
reduce our system to 564000 equations and 565000 unknowns with
323188542 non zero entries. This took less than 3 MIPS-years.

Then our parallelized version of Lanczos algorithm took about 20300
MIPS- years.  Computing and adding Schirokauer maps took less than 20
MIPS-years.  Details of computing logarithm of arbitrary element will
be published later.

We thank Oleg Vasilenko and Vladimir Sidelnikov for useful discussions and 
moral support.

Andrey DOROFEEV

Denis DYGIN

Dmitry MATYUKHIN

Moscow, Russia