Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
From MaRDI portal
Publication:2096516
Abstract: We report on two new records: the factorization of RSA-240, a 795-bit number, and a discrete logarithm computation over a 795-bit prime field. Previous records were the factorization of RSA-768 in 2009 and a 768-bit discrete logarithm computation in 2016. Our two computations at the 795-bit level were done using the same hardware and software, and show that computing a discrete logarithm is not much harder than a factorization of the same size. Moreover, thanks to algorithmic variants and well-chosen parameters, our computations were significantly less expensive than anticipated based on previous records.The last page of this paper also reports on the factorization of RSA-250.
Recommendations
Cites work
- A Kilobit Hidden SNFS Discrete Logarithm Computation
- A Kilobit Special Number Field Sieve Factorization
- A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
- Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
- Better polynomials for GNFS
- Computation of a 768-bit prime field discrete logarithm
- Discrete logarithms and local units
- Factorization of a 768-Bit RSA Modulus
- Factorization using the quadratic sieve algorithm
- Faster cofactorization with ECM using mixed representations
- scientific article; zbMATH DE number 1643927 (Why is no real title available?)
- scientific article; zbMATH DE number 435565 (Why is no real title available?)
- scientific article; zbMATH DE number 475433 (Why is no real title available?)
- scientific article; zbMATH DE number 475434 (Why is no real title available?)
- scientific article; zbMATH DE number 733569 (Why is no real title available?)
- Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
- Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
- Mersenne factorization factory
- On polynomial selection for the general number field sieve
- Online order basis algorithm and its impact on the block Wiedemann algorithm
- Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
- Square Root Algorithms for the Number Field Sieve
- Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm
- The development of the number field sieve
- The middle product algorithm. I: Speeding up the division and square root of power series
Cited in
(13)- New discrete logarithm computation for the medium prime case using the function field sieve
- Individual discrete logarithm with sublattice reduction
- Concrete quantum cryptanalysis of binary elliptic curves via addition chain
- Lattice enumeration and automorphisms for tower NFS: a 521-bit discrete logarithm computation
- Concrete quantum cryptanalysis of binary elliptic curves via addition chain
- We are on the same side. Alternative sieving strategies for the number field sieve
- A more complete cryptanalysis of the RSA-polynomial problem
- RSA quantum cryptanalysis: a thorough exploration of n-bit attacks and emerging factoring techniques
- Faster SCALLOP from non-prime conductor suborders in medium sized quadratic fields
- Parallel structured Gaussian elimination for the number field sieve
- Discrete logarithm factory
- Small public exponent brings more: improved partial key exposure attacks against RSA
- An asymmetric Diffie-Hellman protocol with enhanced efficiency through parallelization
This page was built for publication: Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2096516)
