Computing discrete logarithms with quadratic number rings

From MaRDI portal





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].











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)