Computing discrete logarithms with quadratic number rings
This paper presents some examples of solving discrete logarithms problems using the two best current algorithms. Given a large prime \(p\), and two elements \(a\) and \(b\) in the finite field of \(p\) elements, to find the integer \(x\) such that \(a^x=b\) modulo \(p\). The first subprocedure is to reduce this problem to a set of similar problems of the form \(a^{x_i} = s_i\) modulo \(p\), where \(s_i\) satisfies some smoothness condition. This paper presents a new way of achieving this first step. The paper then goes on to compare the number field sieve method (NFS), with two quadratic number rings, and the method of Coppersmith, Odlyzko and Schroeppel (COS). Two discrete logarithm problems are solved in a field where \(p\) has \(85\) decimal digits. The author concludes that with current technology and at this problem size the COS method is more efficient, although NFS has the better asymptotic complexity. For the entire collection see [Zbl 0889.00042].
- Computation of discrete logarithms in an arbitrary finite field
- scientific article; zbMATH DE number 5532108
- Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
- Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
- Computing discrete logarithms in quadratic orders
- A serial version of the Pohlig-Hellman algorithm for computing discrete logarithms
- Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
- Computing small discrete logarithms faster
- Discrete logarithm in an arbitrary quotient ring of polynomials of one variable over a finite field
- Computing discrete logarithms using \(\mathcal{O}((\log q)^2)\) operations from \(\{+,-,\times,\div,\&\}\)
- scientific article; zbMATH DE number 5532108 (Why is no real title available?)
- scientific article; zbMATH DE number 4077312 (Why is no real title available?)
- The solution of McCurley's discrete log challenge
- Computing discrete logarithms with the general number field sieve
- Performance comparison of linear sieve and cubic sieve algorithms for discrete logarithms over prime fields
- Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
- Об использовании групп классов идеалов квадратичных полей для построения криптографических систем с открытым ключом
- On the convergence of iterations for a method of solution of discrete logarithm representation problem by means of rational approximations
This page was built for publication: Computing discrete logarithms with quadratic number rings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249636)