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
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
0.8740099668502808
0 references
0.8642584085464478
0 references
0.8628171682357788
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