Computing discrete logarithms with quadratic number rings (Q4249636)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1303121
Language Label Description Also known as
default for all languages
No label defined
    English
    Computing discrete logarithms with quadratic number rings
    scientific article; zbMATH DE number 1303121

      Statements

      0 references
      24 November 1999
      0 references
      discrete logarithms
      0 references
      cryptography
      0 references
      number field sieve method
      0 references
      method of Coppersmith, Odlyzko and Schroeppel
      0 references
      Computing discrete logarithms with quadratic number rings (English)
      0 references
      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].
      0 references

      Identifiers