Subject: Discrete logarithm in GF(p^6) with Tower NFS

Dear number theorists,

It is our pleasure to announce a new record discrete logarithm
computation in a 521-bit finite field of the form GF(p^6). Previous
similar computations [1,2] reached 422 and 423 bits respectively and
used the classical Number Field Sieve (NFS) approach, while sieving in
dimension 3.

For our computation we used the extended Tower NFS [3], with an
intermediate number field of degree 3, leading to sieving in dimension 6.
The advantages of using this version of NFS more than compensate the
difficulties of sieving in high dimension, and the time we spent for
collecting relations is less than in the previous computations, while the
target finite field is larger.

Our sieving method uses a new approach based on Schnorr-Euchner's
enumeration algorithm that we adapted for our setting. We also abandoned
the tradition of sieving in an orthotope (rectangle in 2d, cuboid in 3d,
...), and used an L2 sphere as a sieving area.

Here is some data on each step. All timings are scaled to a single
physical core of a machine with 2 CPUs Intel Xeon Gold 6130 with 192 GB
of RAM.

** Target finite field:

  p = 135066410865995223349603927
  ell = 18242935344221832539906081412848119704309124424217403

The decimal digits of the prime p are taken from the digits of the
RSA1024 challenge. We are interested in the 'new' part of the
multiplicative group, and therefore we work modulo ell = p^2 - p + 1.
We chose the example so that ell is also prime, which is the hardest
case.

** Polynomial selection:

The common subfield of degree 3 is given by
   h(y) = y^3 - y + 1
which is irreducible modulo p. On top of this, the Conjugation
polynomial selection was used, leading to
   f1(x) = x^4 + 1
   f2(x) = 11672244015875*x^2 + 1532885840586*x + 11672244015875
and f2 divides f1 modulo p.

** Relation collection:

We used the special-q approach; the sieving area for each special-q was
an L2-sphere of radius 21. We used 1.28 M different special-q ideals, on
the f2-side, starting with qmin = 5e6. We applied our enumeration strategy
on the f2-side, for prime ideals up to 1e7, and then handled promising
candidates with a batch smoothness test on both sides. The large prime
bound was set to 2^27 on both sides.

18.7 M relations were collected in about 2.9 core-years (or 25,300
core-hours).

** Filtering, Schirokauer maps, linear algebra:

We re-used as much as possible the tools from CADO-NFS [4] for these
steps, but several intermediate conversion utilities were written to
take into account the specificities of the Tower setting.

Relations after duplicate-removal: 13.6 M
Size of the matrix after singleton-removal: 5.21 M
Matrix after structured Gaussian elimination:
  size: 1.51 M
  density: 150 coefs/row on average
Number of Schirokauer maps: 5 + 2

The linear algebra was run using the default Block-Wiedemann parameters
from CADO-NFS: a block-factor equal to the number of Schirokauer maps, so
that 7 sequences could be run independently on different machines.
The time for this step is equivalent to 0.16 core-years (1,400
core.hours).

** Individual logarithm:

The representation of GF(p^6) is naturally obtained as a degree-2
extension (defined by f2(x)) of the field GF(p^3) defined by h(y).
We took as a generator the element x + y and for target element a
"random" element whose decimals are taken from Pi (see verification
script).

The element x + y, lifted in the field defined by f1 is a unit (of
infinite order), and therefore its logarithm could be directly deduced
from the kernel vector and an additional Schirokauer map computation.

For the target element, we used Guillevic's algorithm [5] for the initial
splitting, which led to a 35-bit smooth element. The prime factors for
which we didn't have the virtual logarithm were descended in one single
special-q step.

** Total time:

The total time spent for the main phases (sieving + linear algebra) was
26,700 core.hours. But we mention that while the computation was running,
further optimisation to the code was done, and our current code would
save almost 10% on the relation collection step. There is also an easy
factor of 2 to save by using the Galois action; and we expect that the
parameters could be much better tuned than what we did for this first
experiment.

** Acknowledgements:

Many thanks to Aurore Guillevic, in particular for the polynomial
selection choice.
All the computations were done on the Grid5000 facility.

More details will be given in a forthcoming paper.

Best regards,

Gabrielle De Micheli
Pierrick Gaudry
Cécile Pierrot

[1] L. Grémy, A. Guillevic, F. Morain and E. Thomé: Computing discrete
    logarithms in F_{p^6}. SAC 2017, LNCS, pp 85-105

[2] G. McGuire and O. Robinson: Lattice sieving in three dimensions for
    discrete log in medium characteristic. Journal of Mathematical
    Cryptology 15:1, pp. 223-236, 2021

[3] T. Kim and R. Barbulescu: Extended tower number field sieve: a new
    complexity for the medium prime case. CRYPTO 2016, LNCS, pp 543-571

[4] The CADO-NFS development team: Cado-nfs, an implementation of the
    number Field sieve algorithm (2019), available at
    https://gitlab.inria.fr/cado-nfs/cado-nfs

[5] A. Guillevic: Faster individual discrete logarithms in finite fields
    of composite extension degree. Mathematics of Computation 88(317):1,
    2018