Abstract
Recently, several algorithms using number field sieves have been given to factor a number n in heuristic expected time $L_n [1/3; c]$, where \[ L_n [ v ;c ] = \exp \left\{ ( c + o ( 1 ) ) ( \log n )^v ( \log \log n )^{1 - v } \right\} \] for $n \to \infty $. This paper presents an algorithm to solve the discrete logarithm problem for $GF ( p )$ with heuristic expected running time $L_p [ 1/3; 3^{2/3}]$. For umbers of a special form, there is an asymptotically slower but more practical version of the algorithm.
Keywords
Discrete logarithmMathematicsLogarithmBinary logarithmCombinatoricsSieve (category theory)Discrete mathematicsHeuristicField (mathematics)Finite fieldLog-log plotMathematical optimizationComputer sciencePure mathematicsMathematical analysis
Related Publications
Fast evaluation of logarithms in fields of characteristic two
A method for determining logarithms in GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(2^{n})</tex> is presented. Its asymptot...
A subexponential-time algorithm for computing discrete logarithms overGF(p^2)
An algorithm for computing discrete logarithms over GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(p^{2})</tex> , where <tex ...
An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)
A cryptographic system is described which is secure if and only if computing logarithms over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1...
A rigorous time bound for factoring integers
In this paper a probabilistic algorithm is exhibited that factors any positive integer<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math...
The average distances in random graphs with given expected degrees
Random graph theory is used to examine the “small-world phenomenon”; any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain...
Publication Info
- Year
- 1993
- Type
- article
- Volume
- 6
- Issue
- 1
- Pages
- 124-138
- Citations
- 316
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
316
OpenAlex
Cite This
Daniel M. Gordon
(1993).
Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve.
SIAM Journal on Discrete Mathematics
, 6
(1)
, 124-138.
https://doi.org/10.1137/0406010
Identifiers
- DOI
- 10.1137/0406010