Skip to Main content Skip to Navigation
Conference papers

Higher dimensional sieving for the number field sieve algorithms

Laurent Grémy 1
1 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Since 2016 and the introduction of the exTNFS (extended Tower Number Field Sieve) algorithm, the security of cryptosystems based on non-prime finite fields, mainly the paring and torus-based one, is being reassessed. The feasibility of the relation collection, a crucial step of the NFS variants, is especially investigated. It usually involves polynomials of degree one, i.e., a search space of dimension two. However, exTNFS uses bivariate polynomials of at least four coefficients. If sieving in dimension two is well described in the literature, sieving in higher dimension received significantly less attention. We describe and analyze three different generic algorithms to sieve in any dimension for the NFS algorithms. Our implementation shows the practicability of dimension four sieving, but the hardness of dimension six sieving.
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/hal-01890731
Contributor : Laurent Grémy <>
Submitted on : Monday, October 8, 2018 - 10:08:09 PM
Last modification on : Friday, June 25, 2021 - 3:40:05 PM
Long-term archiving on: : Wednesday, January 9, 2019 - 4:21:18 PM

File

article.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01890731, version 1

Collections

Citation

Laurent Grémy. Higher dimensional sieving for the number field sieve algorithms. ANTS 2018 - Thirteenth Algorithmic Number Theory Symposium, University of Wisconsin, Jul 2018, Madison, United States. pp.1-16. ⟨hal-01890731⟩

Share

Metrics

Record views

154

Files downloads

276