De : <joux@freesurf.fr>
Date : 9 novembre 2005 11:40:54 HNE
À : <crypto@ens.fr>
Objet : [crypto] Logarithmes discrets dans GF(370801^30) -- 168 chiffres -- 556 bits

Wednesday, November 9th, 2005.

We are pleased to announce a new record for the discrete logarithm
problem with medium sized base field. We were able to compute discrete
logarithms in GF(370801^30). This was done in less than 12 hours on a
1.15 GHz 16-processors HP AlphaServer GS1280. The approach is a our
variation on Adleman's function field sieve [Ad94], announced in
[JoLe05], about which we are currently preparing a paper.  From a
complexity theoretic point of view, it gives a L(1/3) algorithm in its
range of applicability. As the regular function field sieve, it works
in three phases, sieving, linear algebra and individual logarithms.

As far as we know, the largest previous discrete logarithm
computations were performed, first by Vercauteren and Lercier [LeVe05]
(using the approach of torus representation introduced by Granger and
Vercauteren in [GrVe05]), then by Joux and Lercier [JoLe05] (using
this new variation of the function field sieve).

Precisely, let

p = 370801, GF(p^30) = GF(p)[t]/(t^30-17)

and

  g = t - 6.

Let

 pi(t) = sum(i=0,29,(floor(Pi*p^(i+1))%p)*x^i)     # GP/PARI syntax
       = 162147*t^29 + 338795*t^28 + 245060*t^27 + 323878*t^26 +
       256820*t^25 + 63079*t^24 + 113985*t^23 + 210740*t^22 +
       130675*t^21 + 97042*t^20 + 314407*t^19 + 352378*t^18 +
       335134*t^17 + 342280*t^16 + 61106*t^15 + 272171*t^14 +
       163784*t^13 + 240850*t^12 + 66741*t^11 + 265046*t^10 +
       208274*t^9 + 275057*t^8 + 179507*t^7 + 229391*t^6 + 164345*t^5
       + 198249*t^4 + 3434*t^3 + 341005*t^2 + 258649*t + 52502.

Then,

  pi(t)    =
  g^834934758318669039584738321669880646445961989720307919272366432\
    574478787876554087500076043934132539884636443251840515509803922\
    37533812685076653542562214928407573371226

Sieving:
--------

We define our algebraic function fields by f_1(X,t)=X-t^5 and
f_2(X,t)=X^6+X-17-t^5 and our smoothness basis contain places of
degree 1. We further use the fact that the reduction modulo p of these
places are conjugates each other by the Galois action given by
t->t^(p^6)=213181*t, we finally had to deal with only 148275 degree
one places. In this setting, our sieving software found 329082 useful
divisors of the form $Div X-(at+b)$ with $a$ and $b$ in $\GF{p}$, at
the cost of a 45 minutes computation.

Linear algebra:
---------------

We modified our implementation of the Lanczos algorithm to deal with
this case and we were finally able to solve a sparse system of 150270
equations in 148270 variables (11 entries by row equal to $p^{6i}$,
$i=0,\ldots 4$) at the cost of a 10 hours computation on 8 processors
of a 1.15 GHz HP AlphaServer GS1280. We worked modulo Q =
129717983265199170691 * 3780896193379818021601 *
                                  27084969683231313608318791573698901.

To check these logarithms, we make use of G=g^((p^30-1)/Q).

For instance,

    (t-1)^((p^30-1)/Q)=
    G^858814752732049131584663651366411191299849888095646311187\
      1919059262793471473

and

    (t^5+t-1)^((p^30-1)/Q)=
    G^540446525581805802972783150755982258918174413208848454470\
      7050634558305662620

Individual Logarithms:
----------------------

We found in a few minutes two polynomials,

   num(t) = (t + 55564) * (t + 128273) * (t + 320783) *
            (t^2 + 67030 * t + 124516) * (t^2 + 141998 * t + 97806) *
            (t^2 + 230077 * t + 272221) *
            (t^3 + 281540 * t^2 + 359570 * t + 326930) *
            (t^3 + 283548 * t^2 + 45715 * t + 97297)

and

   den(t) = (t + 20273) * (t + 118843) * (t + 187495) *
            (t + 223094) * (t + 334013) * (t^2 + 4164 * t + 141667) *
            (t^2 + 16050 * t + 165737) * (t^2 + 343958 * t + 368575) *
            (t^4 + 128873 * t^3 + 108876 * t^2 + 126230 * t + 114295)

such that

   pi(t) = 33389 * num(t) / den(t) in GF(p^30).

Then, using special-q descents, we concluded the computation in 40
minutes of CPU-time.

So, as a conclusion, computing discrete logarithms in GF(370801^30)
using the function field sieve can be done very efficiently using a
total slightly less than 0.5 days on a 1.15 GHz HP AlphaServer
GS1280.

Antoine JOUX    (DGA & Universite de Versailles, France,
                 antoine.joux(at)m4x.org),
Reynald LERCIER (CELAR, Rennes, France, reynald.lercier(at)m4x.org).

References:
===========

[Ad94]    L.M. Adleman, ``The Function Field Sieve'', ANTS I, Lecture
          Notes in Math., 1994, volume 877.

[GrVe05]  R. Granger and F. Vercauteren, ``On the discrete logarithm
          problem on algebraic tori'', Crypto'05, LNCS 3621. pp 66--85

[JoLe05]  A. Joux and R. Lercier, ``The function field sieve in the
          medium prime case'', In preparation.

[LeVe05] R. Lercier and F. Vercauteren, ``Discrete logarithms in
         GF(p^18) - 101 digits'', NMBRTHRY list, June 28th, 2005

[JoLe05] A. Joux and R. Lercier, ``Discrete logarithms in GF(65537^25)
          -- 120 digits -- 400 bits'', NMBRTHRY list, October, 2005

De : <joux@freesurf.fr>
Date : 24 octobre 2005 04:25:54 HAE
À : <crypto@ens.fr>
Objet : [crypto] Logarithmes discrets dans GF(65537^25) -- 120 chiffres -- 400 bits

Monday, October 24th, 2005.

We are pleased to announce a new record for the discrete logarithm
problem with medium sized base field. We were able to compute discrete
logarithms in GF(65537^25). This was done in two days and a few hours
on a single Pentium mobile laptop at 1.6 Ghz. The approach is a new
variation on Adleman's function field sieve [Ad94], about which we are
currently preparing a paper [JoLe05]. From a complexity theoretic
point of view, it gives a L(1/3) algorithm in its range of
applicability. As the regular function field sieve, it works in three
phases, sieving, linear algebra and individual logarithms.

As far as we know, the largest previous discrete logarithm computation
was performed by Vercauteren and Lercier [LeVe05] using the approach
of torus representation introduced by Granger and Vercauteren in
[GrVe05].

With this new variation, we could not use our usual sieving code and
we wrote a new, independent sieving program. For the linear algebra,
we used our usual structured gaussian elimination and Lanczos
implementations.

Precisely, let

p=65537

GF(p^25) = GF(p)[t]/
  t^25 + 5*t^21 + 15*t^20 + 10*t^17 + 60*t^16 + 90*t^15 + 10*t^13 +
  90*t^12 + 270*t^11 + 270*t^10 + 5*t^9 + 60*t^8 + 270*t^7 + 540*t^6 +
  407*t^5 + 15*t^4 + 90*t^3 + 270*t^2 + 407*t + 247

and

  g = 3*t.

Let

 pi(t) = sum(i=0,24,(floor(Pi*p^(i+1))%p)*x^i)     # GP/PARI syntax
       = 41667*t^24 + 38062*t^23 + 60623*t^22 + 58559*t^21 +
       20236*t^20 + 47783*t^19 + 49050*t^18 + 37274*t^17 + 4366*t^16 +
       36803*t^15 + 18368*t^14 + 24622*t^13 + 9012*t^12 + 44161*t^11 +
       43372*t^10 + 20341*t^9 + 5644*t^8 + 46803*t^7 + 34689*t^6 +
       45877*t^5 + 9881*t^4 + 64918*t^3 + 32499*t^2 + 36552*t + 9279.

Then,

  pi(t)    =  g^405373694505244074458798850727154577337791051707463993575473\
     6348185260902857777282008537164926838353644893694741284146999.

Sieving:
--------

As usual, the sieving step found multiplicative relations between our
smoothness basis elements. The surprising fact is that this phase was
extremely fast and only took a couple of minutes to generate the
necessary equations.

Linear algebra:
---------------

The linear algebra was further divided in two phases.

We first applied structured Gaussian eliminations to reduce our system
to  79466 equations in 78465 unknowns with 3.8 millions non null entries.

Then, the bottleneck was the computation via Lanczos's algorithm.  Our
parallelized version of this algorithm took 2 days on the pentium
laptop.  At the end, we had logarithms modulo a large factor L of
p^25-1 for the elements of our smoothness basis.

Here, L=(p^25-1)/((p-1)*3571). To check these logarithms, we make use
of G=g^((p-1)*3571).

For instance,

    (t+1)^((p-1)*3571)=
    G^95805410880093234842298898214533393829434304594545362348\
      24840375483524017353229706334323184929723853320944439485
and

    (t^5+t+3)^((p-1)*3571)=
    G^46495712756925209185601240503381083970050573012881700517\
      18556686238431642289730613529631676496393555258546887691.

Individual Logarithms:
----------------------

We found in a few minutes two polynomials,

   num(t) = (t + 20471)*(t + 25396)*(t + 34766)*(t + 54898)*
            (t^2 + 29819*t + 6546)*(t^2 + 44017*t + 38392)*
            (t^2 + 54060*t + 4880)*(t^3 + 23811*t^2 + 6384*t + 3243)

and

   den(t) = (t + 18919)*(t + 31146)*(t + 38885)*(t + 53302)*
            (t^2 + 52365*t + 2605)*(t^3 + 29795*t^2 + 54653*t + 7616)*
            (12850*t^3 + 35335*t^2 + 14881*t + 36655)

such that

   pi(t) = num(t)/den(t) in GF(p^25).

Then, using special-q descents, we concluded the computation in a few
minutes of CPU-time.

So, as a conclusion, computing discrete logarithms in GF(65537^25)
using the function field sieve can be done very efficiently using a
total slightly above 2 days on a single laptop.

Antoine JOUX    (DGA & Universite de Versailles, France,
                 antoine.joux(at)m4x.org),
Reynald LERCIER (CELAR, Rennes, France, reynald.lercier(at)m4x.org).

References:
===========

[Ad94]    L.M. Adleman, ``The Function Field Sieve'', ANTS I, Lecture
          Notes in Math., 1994, volume 877.

[GrVe05]  R. Granger and F. Vercauteren, ``On the discrete logarithm
          problem on algebraic tori'', Crypto'05, LNCS 3621. pp 66--85

[JoLe05]  A. Joux and R. Lercier, ``The function field sieve in the
          medium prime case'', In preparation.

[LeVe05] R. Lercier and F. Vercauteren, ``Discrete logarithms in
         GF(p^18) - 101 digits'', NMBRTHRY list, June 28th, 2005

De : <joux@freesurf.fr>
Date : 22 septembre 2005 08:18:02 HAE
À : <crypto@ens.fr>
Objet : [crypto] Logarithmes discrets dans GF(2^607) et GF(2^613)

Thursday, September 22nd, 2005.

We are pleased to announce a new record for the discrete logarithm
problem over GF(2^n). Using the function field sieve of Adleman
[Ad94], we were able to compute discrete logarithms in GF(2^607) and
GF(2^613). The first computation gives an interesting comparison
between the function field sieve and Coppersmith's algorithm since the
same field finite was already addressed by Thome using the later
algorithm.

As far as we know, the largest such computation previously done was
performed in GF(2^607) by Thome using Coppersmith's algorithm
[Thome02]. The timings reported by Thome (approx. 20000 MIPS years)
are approximatively 12 times larger than the constated runtime during
our FFS experiment (approx. 1500 MIPS years).

The software we used is an adaptation of our GF(p) code to the
characteristic 2 case taking advantage of a generic software based on
a Finite Field C Library called ZEN. In the characteristic 2 case, we
know that very efficient polynomials can be constructed, thus giving
the algorithm the same asymptotic complexity as the SNFS, see [AdHu99]
and [JoLe02]. It also turns out, that most of the ideas developped for
the characteristic p case can be applied. In particular, we used the
same structured gaussian elimination procedure than in the 130 digits
discrete logarithm computation announced here in June [JoLe05].

The two computations were done using different computers. For
GF(2^607), we used a single 1.15GHz 16-processors HP AlphaServer
GS1280 computer during one month. For GF(2^613), we used four
16-processors nodes of the itanium 2 based Bull computer Teranova
during 17 days (1.3GHz CPUs).

Details of the 607 bits computation:
------------------------------------

Let,

GF(2^607) = GF(2)[t]/
 (t^607+t^605+t^494+t^493+t^492+t^490+t^489+t^488+t^486+t^155+t^153+t^151+
  t^149+t^143+t^141+t^139+t^137+t^123+t^121+t^42+t^41+t^40+t^33+t^32+t^29+
  t^28+t^21+t^20+t^18+t^10+t^9+t^8+t^6+t^5+t^4+t^2+1)

and

  g = t.

Let F(x) be the mapping defined from the set of integers to GF(2)[t]
which sends an integer x to a polynomial F(x) such that substituting t
by 2 in F(x) yields x. For instance, F(5) = t^2+1.

Let

 pi(t) = F(\lfloor 2^605 \pi \rfloor)     = t^606+t^605+ ... +t^4+t^2.

Then,

  pi(t)    = g^194891399758968486429687093757270550092585346683729020126\
               283742527056226784304085164731800423582020004466178421521\
               409573307372675772079931586693537551194866503272438476718\
               291852872030.

As for the large characteristic case, this computation was done in three
steps:  _ the sieving step,
  _ the linear algebra,
  _ the final computation of individual logarithms.

Sieving:
--------

The sieving step consisted in finding couples (a(t),b(t)) \in GF(2)[t]^2
such that the divisor of the function (a(t)*u+b(t)) is of smooth norm
in the so-called ``right'' algebraic function field defined by a curve
of genus 0 given by

              u^5 + u + F(5)

and such that the factorization of the polynomial

              a(t) + F(2^121+2^8+2^7+2^5+2^4+1) * b(t)

is smooth too.

The sieving was done efficiently following a ``sieving by vector''
with ``special-q'' technique classically used in the large
characteristic case.  It yields many linear equations between
``logarithms of ideals'' of norms smaller than F(22395195) (1000000-th
irreducible polynomial over GF(2)) in the left field and of norms
smaller than F(16777243) (765925-th irreducible polynomial) in the
right field.

After a 18 days computation on a 1.15 GHz 16-processors HP AlphaServer
GS1280 computer, we obtained 1898338 useful equations with 1556351
unknowns.

Linear algebra:
---------------

The linear algebra was further divided in two phases.

We first applied our new structured Gaussian eliminations to reduce
our system to 365928 equations in 364927 unknowns with 104312947 non
null entries. Time needed for this on only one processor was less than
15 minutes on only one processor.

Then, the critical phase was the final computation via Lanczos's
algorithm. Our parallelized version of this algorithm took 17 days
over 16 processors. At the end, we had ``logarithms for ideals'' of
small norms and, as a consequence, we had logarithms for small
irreducible polynomials.

For instance,

       F(3) = g ^ 1060949212859562222262493702624296695723135234776723302\
              00666223675011082943476527357064661792736790795355204136627\
              16562898663665513345829851531181693190003317157153674790128\
              8957967953,

       F(7) = g ^ 2520048934917069779831062050295651583064497255985365264\
              21876277776038590761926757324360558160692922785915155428024\
              08816416151878677859473587741836141279445015081142869326983\
              907031635,

      F(11) = g ^ 5285790861846577957804828942375119662184718686715282567\
              66962997896082262912436049612433227319619341896423330634824\
              97625024355701766762338498042682870871941097811486539693192\
              6276790609,

      F(13) = g ^ 2776685678422577662147422896753523755481580447535557166\
              59418478534534170093508097298762471177568721780650729614539\
              28534740840511470429127281769449576012561370910747459417754\
              384466,

     ...

F(22395195) = g^328336750529106084982429881581245161065548886074034972647\
                311385749111490214992897570687009560335784476212035915899\
                760943330530210741077758356175062319253271523700882159349\
                834819269812.

Individual Logarithms:
----------------------

We found in less than one hour, two polynomials,

   num(t) = F(9162372248009269) * F(2833280310146019) * F(981656501891) *
            F(39549926607) * F(16870036327) * F(2911549) * F(39805) *
            F(28963) * F(21365) * F(18357) * F(13753) * F(2601) * F(7)

and

   den(t) = F(1246475253358441) * F(287847350809) * F(13015023387) *
            F(32693327483) * F(1783705623) * F(239925077) *
            F(21745087) * F(5481635) * F(2898329) * F(1863) *
            F(721) * F(253) * F(11)^2 * F(3) * F(2)^4

such that

   F(22395195)^27*pi(t) = num(t)/den(t) in GF(2^607).

Then, using special-q descents, computing discrete ``logarithms for
the ideals'' of norms larger than F(22395195) in the left algebraic
field was equivalent to compute discrete ``logarithms for ideals'' of
norms larger than those of the factor basis in the right algebraic
function field. This took only a few minutes of CPU time.

The time needed for computing an individual discrete logarithms in
GF(2^607) on one 1.15 GHz 16-processors HP AlphaServer GS1280 computer
is under an hour, once the sieving step (18 days) and the linear
algebra step (17 days) is performed.

Details of the 613 bits computation:
------------------------------------

Let

GF(2^613) = GF(2)[t]/
 (t^613+t^611+t^610+t^499+t^497+t^495+t^492+t^491+t^490+t^489+
  t^366+t^252+t^249+t^248+t^247 +t^245+t^157+t^155+t^154+t^145+
  t^143+t^142+t^141 +t^139+t^137+t^135+t^134+t^132+t^130+t^129+
  t^128 +t^127+t^126+t^124+t^122+t^43+t^41+t^39+t^36+t^35+t^34+
  t^33+t^31+t^29+t^25+t^23+t^22+t^21+t^19+t^15+t^14+t^12+
  t^7+t^5+t^4+t+1)

and

  g = t.

Let F(x) be as defined above.

Let

 e(t) = F(\lfloor 2^611 \exp(1) \rceil) = t^612+t^610+ ... +t^5+t^3.

Then,

  e(t) = g^90540166494671221719626670665040194356925139180273182043355
       293265810227816669720315781123274014763220199558782053577040234
       12586910522044360597168220282140625205497011520180866370303882

The computation used the same steps as above.

Sieving:
--------

The ``right'' algebraic function field is defined by

              u^5+u^4+u^2+(t^3+t+1).

We also require that

              a(t)+ (t^122+t^8+t^5+t^4+t^3+t)*b(t)

is smooth.

The bound for small ideal was F(33554432) (1465020-th
irreducible polynomial over GF(2)) on both sides.

After a 4 days computation on four 16-processors nodes,
we obtained 5387415 useful equations with 2879101 unknowns.

Linear algebra:
---------------

We first applied our new structured Gaussian eliminations to reduce
our system to 403178 equations in 402154 unknowns with 152161682 non
null entries. Time needed for this on only one processor was about
15 minutes on a single processor.

Our parallelized version of the Lanczos' algorithm then took 13 days
over four 16-processors nodes.

Here is a sample of the result:

       F(3) = g ^ 2063740429642602377228525818500941651870240635044800
                  4911929146998757589544076526162419233825266927893750
                  0828663539095933795101419292210327527910101443768887
                  10317433660025156726402045497

       F(7) = g ^ 1970226238871415159139256592389766065573453254436002
                  5678333053786726818232388688740594435045036580994749
                  3179380666581915298804648319648952834860017803406472
                  55636703755773749643637310553

      F(11) = g ^ 1376760539080237423601908777579676277131772106336408
                  9507060669784404491938398624603130505166785033291547
                  8815645007826483954728577128443183885130690419778825
                  26434726822099690509507248154

      F(13) = g ^ 3442750725293094917838196293196348614623633274655312
                  3145305274666669398896947205168326407692963984901532
                  0466692419569570138376558148427721257268715811356360
                  2241411454308361749120771972
           ...

F(33553757) = g ^ 1406085348152248639989295095399521815262803460302160
                  4894203923165228201314849853906320268001645079258250
                  2228211729452876381481958191872037119864775142445006
                  47199086198854444723241177549

Individual Logarithms:
----------------------

We found in less than one hour, two polynomials,

   num(t) = F(15506735) * F(6109055) * F(31475) * F(1835) * F(19) * F(7) *
            F(8167719318131749415) * F(62627218263025061503) *
            F(49277132941) * F(6893932779863494865230135)

and

   den(t) = F(33513655) * F(6441771) * F(375235) * F(82597) * F(57397) *
            F(1053) * F(971) * F(193) * F(25) * F(2)^2 *
            F(4074544069) * F(167141529695) * F(197958190319) *
            F(234985401838936862111309147)

such that

   F(33553757)^22*e(t) = num(t)/den(t) in GF(2^613).

We concluded the computation by special-q descent as above.

Antoine JOUX    (DGA & Universite de Versailles, France,
                 antoine.joux(at)m4x.org),
Reynald LERCIER (CELAR, Rennes, France, reynald.lercier(at)m4x.org).

References:
===========

[Ad94]    L.M. Adleman, ``The Function Field Sieve'', ANTS I, Lecture
          Notes in Math., 1994, volume 877.

[AdHu99]  L.M. Adleman and M.A. Huang. Function field sieve method for
          discrete logarithm over finite fields. Information and
          computation, 1999, volume 151, pages 5-16.

[Co84]    D. Coppersmith, ``Fast Evaluation of discrete logarithms in fields
          of characteristic 2''. IEEE Transactions on Information Theory,
          1984, volume 30, pages 587-594.

[JoLe02] A. Joux and R. Lercier, The function field sieve is quite
         special. ANTS-V, LNCS 2369, pages 431--445, 2002.

[JoLe05] A. Joux and R. Lercier, ``Discrete logarithms in GF(p)'',
         Saturday, June 18th 2005. NMBRTHRY Mailing List.

[Thome02] E. Thome, ``Discrete logarithms in GF(2^607)'',
         Saturday, Feb. 23th 2002. NMBRTHRY Mailing List.

De : <joux@freesurf.fr>
Date : 18 juin 2005 17:24:30 HAE
À : <crypto@ens.fr>
Objet : [crypto] Calcul de logarithmes discrets dans GF(p) --- 130 chiffres

Samedi 18 juin 2005

La factorisation du nombre RSA-200 par Franke et al a amplifiée
l'écart entre les records de factorisation et de calcul de
logarithmes discrets dans les corps finis.

Dans une première tentative pour réduire cet écart, nous sommes heureux
d'annoncer un calcul de logarithmes discrets modulo un nombre premier
de 130 chiffres. Ce calcul a duré trois semaine, sur une machine de
type AlphaServer GS1280 à 16 processeurs de 1.15 GHz. A notre
connaissance, il s'agit du record actuel de calcul de logarithme discret
modulo un nombre premier de forme générale.

L'approche suivie ici est très proche de notre calcul précédent
modulo un nombre de 120 chiffre réalisé en 2001 [JoLe01].
A part l'outil d'élimination gaussienne structurée que nous avons
remplacé par un algorithme plus efficace, ce calcul a été essentiellement
réalisé avec les mêmes algorithmes et implémentations.

                                *
                               ***

Plus précisement, nous avons choisi le nombre premier:

  p = \lfloor 10^{129} \pi \rfloor + 38914,
    = 31415926535897932384626433832795028841971693993751058209749445923\
      07816406286208998628034825342117067982148086513282306647093883523

ainsi qu'un générateur du groupe multiplicatif modulo p:

  g = 2.

Nous nous sommes fixé comme objectif le nombre:

  y = \lfloor 10^{129} e \rfloor,
    = 27182818284590452353602874713526624977572470936999595749669676277\
      24076630353547594571382178525166427427466391932003059921817413596.

que nous avons pu écrire comme

  y = g^21138488223786795657590463012228607444377276414435077577308395472\
        0095258549520212875421011837642236137330107919426669776684829109

de plus,

y+1 = g^44702322729716182227202277779696809350061507316078741399367293664\
        6278250727984316514493453566339150205697936921746933988890152955.

                                *
                               ***

Ce résultat a été obtenu par le désormais classique crible algébrique,
comme décrit, sur le plan théorique, par Schirokauer [Schi93].
Le calcul s'est déroulé en trois étapes:
  _ le crible,
  _ l'algèbre linéaire,
  _ le calcul final des logarithmes individuels.

Crible:
-------

Lors de la phase de crible, nous avons trouvé des couples (a,b) tels que
l'idéal principal engendré par (a+bt) dans le corps de nombre de ``droite''
défini par
                P(t) = t^3+12*t^2-13*t+3

soit de norme friable et que l'idéal engendré par (ac+bs) dans le corps
de ``gauche'' défini par
                Q(s) = s^2
                     - 16909365834968487790611823369329079646668885*s
                     + 20077251478186688202553272153633131115561222*c

le soit également, où:

                   c = 8258891862441565856565120580503979696050188.

Ces deux polynômes sont relié à p, par le fait que P(t) et Q(c*t)
ont une racine commune modulo p.

Le groupe de Galois de P est d'ordre 3.
Le groupe des unités du corps de nombre associé est engendré par
les deux unités fondamentales 9*t^2+117*t-41 and 3*t-1.
Le nombre de classes vaut 1 et tous les idéaux sont principaux dans
ce corps de nombre.

La seule information connue sur le polynôme Q est qu'il défini un
corps quadratique imaginaire.

L'algorithme de crible utilisé est un crible le long d'un réseau
(``sieving by vector'') avec spécial-q. Il produit des relations
linéaires entre les ``logarithmes des idéaux de petites normes''
(inférieure à 18815207, 1200000ième idéal premier du côté gauche
et inférieure à 5799977, 400000ième idéal premier du côté droit).

Après 13 jours de calcul, nous disposons de 1946916 équations
utiles pour 1466090 inconnues.

A cette étape, il s'agit de modifier les équations, par l'ajout
de variables additionnelles, afin d'obtenir un système compatible.
Pour ce faire, Schirokauer a introduit une méthode générale.
Cependant, dans notre calcul, nous avons préféré procéder différemment
en exprimant explicitement les unités du côté droit en fonction des
deux unités fondamentales, ce qui est possible car tous les idéaux sont
principaux de ce côté. Du côté gauche, s'agissant d'un corps quadratique
imaginaire, il est inutile de procéder à un ajustement complexe des
équations. Il suffit d'ajouter à chaque équation une inconnue de
renormalisation, la même à chaque fois, pour tenir compte de la constante c
intervenant dans Q(s).

Il a suffit de 2 heures pour ajouter la contribution des unités aux
équations.

Algèbre linéaire:
----------------

L'algébre linéaire est elle-même décomposée en deux phases.

Dans un premier temps, l'élimination gaussienne structurée nous a
permis de nous ramener à un système de 433181 équations en 432172
inconnues comportant 35323996 entrées non nulles.
Grâce à un nouvel algorithme, cette réduction a demandée moins de
15 minutes sur un seul processeur.

Finalement, ce système a été résolu par l'algorithme de Lanczos.
Notre implémentation parallèle a pris 8 jours pour cette résolution.
En sortie, nous avons obtenu les ``logarithmes des idéaux'' de petites
normes. En conséquence, nous en avons déduit les logarithmes de certains
petits nombres premiers.

Par exemple,

  3 = g^18935022642385712265442162784856643707918464682969857705736136901\
        41150005617588988077853204617146221819982684416360486509655807744

 11 = g^4237102728490621953875844147019736370886375829289178182680995735\
        01636485194195766410542501760951486387180557151162653894308532555

 37 = g^9506461927181030030008386959918266024894356371823647783744271773\
        64890693263742686571949298174887812261560755967507029212728831603

etc ...

Logarithmes individuels:
-----------------------

Comme dans [JoLe02], nous utilisons la structure particulière du
groupe de Galois de t^3+12*t^2-13*t+3.

Soit r la racine commune modulo p de P(X) and Q(c*X), nous avons
pu trouver en quelques heures, à l'aide d'un code non optimisé, deux
nombres algébriques,

      num = 3067768196913421887864*r^2
          + 3564986601609873727783*r
          + 11102447291325953922104

et

      den = -1886510641162700085744*r^2
            - 614947335528224906300*r
            + 1174119585425048306413

tel que

		         g^2*y = -num/den modulo p,

et vérifiant les relations suivantes:

num = -(-1+r)
    * (-r^2-11*r+4)
    * (r^2+7*r-1)
    * (38*r^2-5*r-14)
    * (-58*r^2+51*r-10)
    * (-19968234615452*r^2-253095266814753*r+88773815898184)
    * (-103527432682334747*r^2-1277679011473992359*r+909588468749207990)
    * (52211650*r^2+648088367*r-410299369)
    * (-10551006859*r^2-133733301857*r+46901909959)
    * (9*r^2+117*r-41)^(-12) * (3*r-1)^37

et

den = (-1+2*r)^2
    * (-250393155*r^2-3090199419*r+2200155182)
    * (-17257853*r^2-218912874*r+74493007)
    * (-6714524974*r^2-85147186243*r+29313654043)
    * (-110524082322*r^2-1346736343362*r+1196134561937)
    * (-1643288515585*r^2-20830007491278*r+7286141994812)
    * (9*r^2+117*r-41)^(-17) * (3*r-1)^49

Ces égalités sont obtenues en décomposant dans le corps de nombres de
droites les entiers algébriques obtenus en remplacant r par t dans
num et den. Chacun des facteurs engendre un idéal premier de norme assez
petite.

Puis, par une descente à base de spécial-q, nous avons calculé les
``logarithmes de ces idéaux'', de normes 2592589, 17109767, 88447559,
18475577467, 108621101466083, 3525111154062353, 140633755138925249,
59677745837274488381 et 1019544752700081075653 dans le corps de nombre
de droite (par un calcul de quelques minutes, sur un processeur, pour
chaque).
A l'issue de nombreuses itérations, nous obtenons:

num = g^13662163601403810017674251686005246963595557866172606992339095483\
        08183912002005416888157658497005919998119321431364412826732967004

et

den = g^27256278046974096644228422301179900640143677221604628339482978897\
        41996856595589703326754059330422217851863256768578896373595079654.

Ce qui permet de déduire le logarithme de y.

                                *
                               ***

En conclusion, le temps de calcul de logarithmes individuels modulo un
nombre premier de 130 chiffres, sur un HP AlphaServer GS1280 16 processeurs
à 1.15GHz est de quelques heures, après un précalcul du crible (13 jours)
et
de l'algèbre linéaire (8 jours).

Antoine JOUX    (DGA et Universite de Versailles, France,
                 antoine.joux(at)m4x.org),
Reynald LERCIER (CELAR, Rennes, France, reynald.lercier(at)m4x.org).

Références:
===========

[JoLe02]  A. Joux and R. Lercier, Improvements to the general number
          field sieve for discrete logarithms in prime
          fields. Math. Comp., 72(242):953-967, 2002.

[JoLe01] A. Joux and R. Lercier, ``Discrete logarithms in GF(p)'',
         Tuesday, April 17 2001. NMBRTHRY Mailing List.
         Available at http://www.medicis.polytechnique.fr/~lercier.

[Schi93] O. Schirokauer, Discrete Logarithms and local units. Phil.
         Trans. R. Soc Lond. A 345, pages 409-423, 1993.