<abstract xmlns="http://www.w3.org/1999/xhtml"><p>An adaptation of the Number Field Sieve (NFS) algorithm to solve a discrete logarithm problem in degree 6 finite fields (DLP6) requires a modified sieving procedure to find smooth elements of the three dimensional sieve space. In our successful solution [P. Zajac: <italic>Discrete Logarithms and Degree Six Numbere</italic><italic>Field Sieve: A practical Approach. </italic>VDM Verlag Dr. M¨uller, Saarbr¨ucken, 2009] we have used a modified line sieving to process a box-shaped region using a large factor base. In this contribution, we compare the results with an alternative approach based on the lattice sieving, which was used in most of the classical factorization and DLP record solutions. Results indicate that this approach does not scale to the 3D-case, making DLP6 more difficult in practice than comparable classical DLP cases.</p></abstract>

An adaptation of the Number Field Sieve (NFS) algorithm to solve a discrete logarithm problem in degree 6 finite fields (DLP6) requires a modified sieving procedure to find smooth elements of the three dimensional sieve space. In our successful solution [P. Zajac: Discrete Logarithms and Degree Six NumbereField Sieve: A practical Approach. VDM Verlag Dr. M¨uller, Saarbr¨ucken, 2009] we have used a modified line sieving to process a box-shaped region using a large factor base. In this contribution, we compare the results with an alternative approach based on the lattice sieving, which was used in most of the classical factorization and DLP record solutions. Results indicate that this approach does not scale to the 3D-case, making DLP6 more difficult in practice than comparable classical DLP cases.

On the use of the lattice sieve in the 3D NFS

Department of Applied Information and Information Technology, Slovak University of Technology, Ilkoviˇcova 3, SK–812-19 Bratislava, SLOVAKIA

Tatra Mountains Mathematical Publications

{"article-title":"On the use of the lattice sieve in the 3D NFS"}

An adaptation of the Number Field Sieve (NFS) algorithm to solve a discrete logarithm problem in degree 6 finite fields (DLP6) requires a modified sieving...

On the use of the lattice sieve in the 3D NFS

Publié en ligne: 12 nov. 2012

Pages: 161 - 172

DOI: https://doi.org/10.2478/v10127-010-0012-y

Mots clés
algebraic numbers, number field sieve, lattice sieve.

This content is open access.

On the use of the lattice sieve in the 3D NFS

Publié en ligne: 12 nov. 2012

Pages: 161 - 172

DOI: https://doi.org/10.2478/v10127-010-0012-y

Mots clésalgebraic numbers, number field sieve, lattice sieve.

This content is open access.

Mots clés
algebraic numbers, number field sieve, lattice sieve.