Evaluation Report on the Discrete Logarithm
Problem over finite fields
Jacques Stern

1

Introduction

This document is an evaluation of the discrete logarithm problem over finite fields(DLP), as a basis for designing cryptographic schemes. It relies on the analysis ofnumerous research papers on the subject.
The present report is organized as follows: firstly, we review the DLP and several
related problems such as the Diffie-Hellman problem. Next, we analyze the various
algorithms that are currently known to solve the problem. For each algorithm, we study
its asymptotic behaviour, as well as its practical running time, based on experiments
reported in the literature. Finally, we derive consequences in terms of key sizes forcryptosystems whose security depend on the hardness of the DLP. We conclude bymaking some predictions on how the key sizes might evolve. This is as requested byIPA.

2

The DLP and related problems

In this section, we review the DLP and several related problems, such as the computational and decisional Diffie-Hellman problems and we investigate their security interms of complexity-theoretic reductions.

2.1

The DLP as a cryptographic primitive

The discrete logarithm problem in a finite group G can be stated as follows: compute x
from g and u = g x . Integer x is called the discrete logarithm of u in base g, x = logg (u).
Of particular interest in the present report, is the case when G is the multiplicative
group of a a finite field K with q = pn elements, where p is a prime. In this setting,
cryptographic applications are almost exclusively related with the case p = 2 and thecase n = 1. The first case corresponds to a field of characteristic 2, while the second uses
the group Z?p of invertible elements of Zp . Each case is an instance of a larger family:
1

fields of small characteristic p and fields of small degree n, respectively. Subgroups arealso used. For example, p can be chosen such that p − 1 has a large prime factor q ofprescribed size. In this case, there is a subgroup of order q, consisting of elements x in
p−1
Z?p such that x q = 1 mod p.
The basic security assumption on which cryptosystems based on the DLP rely is
one-wayness (OW): an attacker cannot recover x from g and g x . In a more precise
complexity-theoretic framework, this means that the success probability Succdlp (A) of
any polynomial time adversary A attempting to invert x :−→ g x is negligible, i.e.
asymptotically smaller than the inverse of any polynomial function of the security
parameter k. The security parameter can be taken as the degree n of the field, forsmall characteristic, and as the bit-size of p for small degree. Probabilities are takenover g and x. In the case of fields of small degree, it is implicit that a prime generation
algorithm K(1k ) produces p. It uses randoin coins Ω and probabilities also range overthese random coins.
To go from asymptotic to exact estimates, we can define Succdlp (τ, k) as the probability for an adversary to find the preimage of a given element within time τ . We turnthe above into symbols, in the case of prime fields (n = 1):
Succdlp (A) = Pr[p ← K(1k ), g ∈R G, x ∈R {0, . . . , p−1}, u ← (g x mod p) : A(p, u) = x].
The hardness of the DLP is the statement that, for large enough k, this probability isextremely small.
Many cryptographic schemes rely on the assumption that the DLP is hard. To
name a few, the El Gamal public key cryptosystem and signature scheme [10], theDigital Signature Algorithm DSA [9], the Cramer-Shoup cryptosystem [8, 35].

2.2

The Diffie-Hellman problem

The modern approach to cryptographic design relies on the notion of security proof.
Such proofs are reductions in the sense of complexity theory. Given an attacker A
that breaks the cryptographic scheme, one designs another machine B, solving theunderlying hard problem. The relation between running times and success probabilities
of A and B is further made explicit, so that, if the security loss is not too large, concrete
estimates on key sizes may be derived from the proof.
Ideally, one would like to establish the security of a scheme based on the soleassumption that the underlying problem is hard. Unfortunately, very few schemes allow
such a proof. One of them is the Cramer-Shoup cryptosystem, quoted above [8]. For theothers, the best one can hope for, is a proof carried in a non-standard computationalmodel, as proposed by Bellare and Rogaway [2], following an earlier suggestion by
Fiat and Shamir [11]. In this model, called the random oracle model, concrete objects
such that hash functions are treated as random objects. This allows to carry through2the usual reduction arguments to the context of relativized computations, where thehash function is treated as an oracle returning a random answer for each new query.
A reduction still uses an adversary as a subroutine of a program that contradicts amathematical assumption, such as the hardness of the DLP. However, probabilities aretaken not only over coin tosses but also over the random oracle.
In the case of the discrete logarithm, whatever the computational model is, it isoften the case that security is not related to the DLP itself, but rather to the socalled decisional Diffie-Hellman problem, or its computational version. The decisional
Diffie-Hellman assumption over a group G asserts that it is hard to distinguish the
distributions D and R, whereR = {(g1 , g2 , u1 , u2 )}with all four elements taken at random in G and
D = {(g1 , g2 , u1 , u2 )}with logg1 (u1 ) = logg2 (u2 ). A quantitative version measures the maximum advantage
AdvDDH(τ ) of a statistical test T that runs in time τ . This means the maximum of thedifference of the respective probabilities that T outputs 1, when probabilities are takenover D or R.
Related to the above is the computational Diffie-Hellman assumption (CDH), whichstates that it is hard to compute g xy from g, g x , and g y . It is obvious that DDH is astronger assumption than CDH, which in turn, is stronger than the assumption thatthe DLP is hard. However, no other relation is known and the only way to solve thehard problems underlying DDH or CDH is to compute discrete logarithms. There aresome indications, in other settings, that DDH might be easy, in some cases, while theCDH remains difficult (see [13] and [12]). However, the references just quoted are not
relevant to the context of finite fields.
In conclusion, the only method known to attack the Diffie-Hellman problems is
to solve the DLP. Therefore, in order to estimate whether the parameters of a cryptographic scheme, relying on the hardness of these problems, offer a wide security margin,
one needs to refer to the performances of the various algorithms known for the DLP.

3

Algorithms for the DLP

3.1

Exponential algorithms

There is an algorithm due to Pohlig and Hellman (see [29]), which reduces the determination of the discrete logarithm in a field to the analogous problem in subgroups.
For example, if p − 1 is a product of small factors qi , relatively prime to each other, the3

algorithm separately operates on subgroups of order qi However, this is irrelevant in a
cryptographic context, since generation algorithms can simply avoid such primes p.
The best algorithm known to date for solving the DLP in any given group G
pis thePollard ρ-method from [30] which takes computing time equivalent to about πn/2group operations. In 1993, van Oorschot and Wiener in [38], showed how the Pollard
ρ-method can be parallelized so that, if t processors are used, then the expected
number√πn/2

of steps by each processor before a discrete logarithm is obtained is ' t . In order
to compute the discrete logarithm of y in base g, each processor computes a kind of
random walk within elements of the form g a y b , selecting xi+1 as yxi or x2i or else gxi ,according to a deterministic but randomly looking choice (say based on a hash value).
“Distinguished” points xi are stored together with their representations xi = g ai y bi in alist that is common to all processors. When a collision occurs in the list, the requested
discrete logarithm becomes known. There is no record involving discrete logarithms in
subgroups of Z?p . However, one can estimate what such a record would be, by recallingthe current record for computations in the group of points of an elliptic curve. In april
2000, the solution to the ECC2K-108 challenge from Certicom led to the computationof a discrete logarithm in a group with 2109 elements. This is one of the largest effort
ever devoted to a public-key cryptography challenge. The amount of work required
to solve the ECC2K-108 challenge was about 50 times that required to solve the 512bit RSA cryptosystem (see [3]) and was thus close to 400000 mips-years. Because,the standard arithmetical operations execute faster than elliptic curve additions, anequivalent effort in the area of subgroups of Z?p would presumably reach a few bits
more. Referring to [26], we find that it would mean an extra 4 to 5 bits.
It should be noted that the exponential algorithms decribed in this section aresuperseded by the subexponential algorithms that appear further on in the present
report. However, when dealing with subgroups, their computing time is related to thesize of the subgroups rather than the size of the field. Accordingly, they give indications
on the minimum size of the subgroup. Based on [26], it appears that moderate sizes
such as 256 bits, should withstand attacks for the next 50 years.

3.2

The index calculus method

Efficient algorithms to solve the discrete logarithm problem over finite fields use theso-called index calculus method (see [27, 34] for a survey). In this section, we explain
the basic principle of this method. Its latest instantiations, the number field sieve andthe function field sieve, will be detailed later. We let G = K∗ and we assume that thebase g is a generator of G, so that all logarithms are well-defined. This is no restriction,
since randomly chosen elements are generators with high probability.
The index calculus method uses a fixed small set called the factor base B ⊆ G, andtries to write elements as a product of members of the factor base. The base consists4

of objects which are small and irreducible, in an appropriate sense:• In a prime field Fp , where we identify field elements with integers in {0, . . . , p−1},
a factor base consists of all prime numbers less than some prescribed bound.
• In a field of characteristic 2, F2n , where we write field elements as polynomialsof degree < n, a factor base consists of all irreducible polynomials of degree lessthan some prescribed bound.
The algorithm has two steps:
1. A precomputation step, where the logarithms logg b of all members of the factor
base are obtained
2. A computation step, which tries enough g a y until the result factors over the factor
base, thus providing the requested logarithm logg y.
The first step itself has two stages:• A sieving step, where one gathers multiplicative
Q relations between elements ofthe factor base. Such relations are of the form bi ∈B bei i = 1, where the productranges over B and each ei is an integer.
• A linear algebra step, where, taking logarithms, each relation produces a linear
equation with unknowns the discrete logarithms of the factor base. When enoughrelations have been found, the logarithms of the factor base are obtained by linear
inversion.
Observe that the various logg b, b ∈ B, are computed up to some multiplicative constant.
To find the value of the constant, one usually adds g as an element of B. Also notethat the first stage can easily be distributed.
Enlarging the factor base makes the sieving easier, but increases the number ofrelations needed to successfully perform the linear algebra. A fundamental problem in
the analysis of index calculus algorithms is to estimate the probability that the sieving
process produces enough relations. Such estimates rely on the heuristic assumptionthat elements appearing in the sieving process behave randomly. This assumption has
been verified extensively. The resulting complexity estimates are naturally expressedin terms of the L-function:
Lq [s; c] = exp(c(ln q)s (ln ln q)1−s ).
The reason why this function is involved is its relation with the asymptotic probability
that a random element can be factored into elements of a factor base (see [18, 28]).
For instance, it is known that the probability that a random integer < Lx [ν; λ] has all
its prime factors < Lx [w; µ] is asymptotically
Lx [ν − w; −λ(ν − w)/µ + o(1)].
53.3

The Number Field Sieve

In the case of prime fields, the method described in the previous section has been
extended in [7], working with an imaginary quadratic number field. The extension has
been termed Gaussian Integer Method. Its time complexity is Lp [1/2; 1 + o(1)]. It has
been used until 1998 to establish records:• 85 digits in 1996 (see [42])• 90 digits in 1998 (see [19])The Gaussian Integer Method has been generalized in [16, 32]. The resulting algorithm, called the number field sieve, adapts the general number field sieve (GNFS)
factoring algorithm [25] to the computation of discrete logarithms in fields of small
degree. It was first proposed by Gordon [16], in the case of prime fields Fp , with aconjectured running time Lp [1/3; 32/3 + o(1)]. The improved heuristic running timeLp [1/3; (64/9)1/3 + o(1)] was obtained by Schirokauer [32]. Recently, Schirokauer [33]extended the number field sieve to any field of fixed degree. The complexity is stillmeasured by the same function, replacing p by the cardinality pn of the field. To keep
the exposition simpler, we restrict oursekves to the case of a prime field Fp : giveny ∈ F∗p and a generator g of F∗p , we wish to compute the unique x ∈ {1, . . . , p − 1} suchthaty ≡ g x (mod p).
3.3.1

Overview

The number field sieve (NFS) first selects two low-degree irreducible polynomials f1 (X)and f2 (X) in Z[X] with small coefficients such that f1 (X) and f2 (X) have a common
root m in Fp . These polynomials define two number fields Q(α1 ) and Q(α2 ). Because
m is a root, there is a natural ring homomorphism ϕj from Z[αj ] to Fp (j ∈ {1, 2}),
induced by ϕj (αj ) = m. We extend ϕj to the field Q(αj ), ignoring potential divisibility
problems.
The ring of integers of a number field is not necessarily a unique factorization
domain, but the ring of fractional ideals always is. Thus, NFS selects two ideal factor
bases B1 and B2 (corresponding to Q(α1 ) and Q(α2 )), consisting of prime ideals ofsmooth norm. We define other notions of smoothness as follows: a fractional ideal I of
Q(αj ) is smooth if it can be factored over the factor base Bj , and an algebraic number
x is smooth if the fractional ideal hxi it spans is smooth.
By sieving, the NFS finds a huge collection of pairs (ai , bi ) of small integers suchthat each ai − bi αj is smooth: as a result, the factorization of hai − bi αj i is known.
We first focus on the number field Q(α1 ). Linear algebra modulo p − 1 produces many

6

integer vectors (ei ) such that the fractional idealYhai − bi α1 iei
iispower. This does not necessarily imply that the algebraic number
Q a (p − 1)-th
ei
(a
−
b
α
)
is
a (p − 1)-th power in Q(α1 ). However, using specific linear maps fromi 1
i i
Q(α1 ) to Zp−1 , Schirokauer [32] was able to add a few linear equations to ensure thatQei
i (ai − bi α1 ) is in fact a (p − 1)-th power in Q(α1 ). If this holds, then:!
Y
ϕ1(ai − bi α1 )ei ≡ 1 (mod p),ithat is,Y(ai − bi m)ei ≡ 1 (mod p).
iTaking logarithms yields:X

ei logg (ai − bi m) ≡ 0 (mod p − 1).

iBut each ai − bi m is smooth because ai − bi αj is smooth. Therefore the previous
equation can be rewritten as:X
e0q logg q ≡ 0 (mod p − 1),q∈B

where B is a set of small prime numbers, and each e0q is a known integer. Many suchlinear equations are obtained and more with the second number field Q(α2 ). Whenenough equations have been found, another use of linear algebra outputs logg q formany q ∈ B, up to some multiplicative constant. Such q’s are called good primes. In
our description, we mentioned using linear algebra twice, to produce (p − 1)-th powers
on one hand, and to compute the logarithms of good primes, on the other hand. They
can actually be merged into a huge single step.
It remains to explain the computation of an individual logarithm. Note that applying the method to a single known power of g, will first remove the multiplicative
constant. To compute the discrete logarithm x of y = g x mod p, it is enough to findexponents ei ∈ Z such that:Yy≡pei i (mod p),pi ∈Bwhere each pi is a good prime, and not just pi ∈ B, since only the logarithms ofthe good primes are known. There are several methods to find such exponents. We
7describe the technique presented in [23], which seems to be the most efficient known,
as it does not require any huge linear algebra step contrary to earlier method of [40].
Using two-dimensional lattice reduction, one can compute two linearly independent√
integer vectors (A1 , B1 ) and (A2 , B2 ) with coordinates ≈ p such that:
y≡

A1
A2
≡
(mod p).
B1
B2

It follows that for any integers α and β:y≡αA1 + βA2(mod p).
αB1 + βB2

Now, since Ai and Bi are reasonably small, one can try to find pairs (α, β) such thatboth αA1 +βA2 and αB1 +βB2 are smooth with respect to good primes, using a sieving
technique. If no candidate is found within a reasonable time, one tries again, replacing
y by ysi , where s is the largest good prime.
3.3.2

Practical experiments

The first practical experiment of NFS for discrete logarithms was presented at Eurocrypt ’95 [39]. Further results appeared in [40, 41, 22]. The current record is [21],where discrete logarithms in a 120-digit prime field could be computed, following theapproach of [23]. Paper [41] reports experiments with a larger 129-digit prime field,
but its cardinality has a special form, which allows for better complexity. The current
record of [21] was obtained in 10 weeks, on a single 525-MHz quadri-processor Digital
Alpha Server 8400 computer. Sieving took 42 days and produced 2685597 equations
with 1242551 unknowns. Structured Gaussian elimination [24, 23] took one extra day
to reduce the system to 271654 equations in 271552 unknowns with 22690782 non-zero
entries. Then, using a a parallel version of Lanczos’s algorithm [14], linear algebra was
performed in 30 days over 4 processors. One this has been done, the computation ofeach additional individual logarithm takes about 12 hours.

3.4

The Function Field Sieve

The function field sieve adapts the general number field sieve GNFS factoring algorithm [25] to the computation of discrete logarithms in finite fields of small characteristic. It was first discovered by Coppersmith [5] in the case of fields F2n , with aconjectured running time L2n [1/3; c + o(1)], where c ≈ 1.4. Note that Coppersmith’salgorithm predates the number field sieve. Adleman [1] proposed the function fieldsieve as a generalization of Coppersmith’s algorithm to any finite fields of small characteristic. More precisely, the function field sieve computes discrete logarithms in Fpn
8with expected running time Lpn [1/3; c + o(1)] for some constant c, when log p ≤ ng(n) ,where g is any function from N to ]0; 0.98[ which converges to zero.
To keep the exposition simple, we only present Coppersmith’s algorithm. Thisalgorithm can be viewed as a special case of the function field sieve [1] (see [34]),
though the constant in the complexity of the function field sieve is worse.
3.4.1

Overview of Coppersmith’s algorithm

We want to compute discrete logarithms in the field K = F2n , which we represent,in the usual way, as F2 [X]/hf (X)i, where f (X) is a monic irreducible polynomial of
degree n over F2 . Polynomial f (X) is chosen of the form X n + f1 (X) where f1 (X)has very small degree. It is conjectured, but not proven, that such an f1 (X) with
degree O(log n) always exists. Recall that squaring in K is a linear operation, which iscomputed for free and that factoring is easy.
We select a factor base B consisting of all irreducible polynomials of degree lessthan a prescribed bound, and define smoothness accordingly: a polynomial is smooth
if it can be factored into elements of B. Let r be such that 2r ' n1/3 and h = d 2nr e.
Sieving, we search for polynomials A(X) and B(X) of degree approximately n1/3 , suchthat
C(X) = A(X)X h + B(X),
and
r

r

r

r

D(X) = C(X)2 ≡ A2 X h2 −n f1 + B 2 (mod f (X)).
are both smooth. The original sieving procedure of [5] was improved by [15]. Observethat the degrees of C(X) and D(X) are approximately n2/3 . When C(X) and D(X) arersmooth, the relation D(X) ≡ C(X)2 (mod f (X)) produces a linear equation modulo
2n − 1, with unknowns the logarithms of the members of the factor base. A huge linear
algebra step yields all values of log b(X) for b(X) ∈ B.
To compute the individual logarithm of y, one uses the fact that factoring can be
efficiently performed in K. One thus selects a random integer s until yg s (mod f (X))
is smooth, and then derives logg y.
3.4.2

Practical experiments

Experimental results are reported in [5, 15, 36]. The most recent record is [22], which
computes logarithms over F2521 . The entire computation was done in one month on asingle 525MHz quadri-processor Digital Alpha Server 8400 computer. The approach
was based on a careful implementation of the general function field sieve [1], rather
than the use of Coppersmith’s algorithm. Sieving took 3 weeks and yielded 472121
equations with 450940 unknowns. Structured Gaussian elimination [24, 23] reduced
the system to 197039 equations in 196939 unknowns with 12220108 non null entries, in9one hour. Then, it took 10 days to run Lanczos’s algorithm [14] and complete the linear
algebra. The computation of an individual logarithm takes an additional 12 hours.
Very recently, [36] presented a new implementation of Coppersmith’s algorithm
and preliminary experiments to compute discrete logarithms over F2607 . Sieving wascompleted and took 19,000 MIPS years. As a comparison, the factorization of RSA155 required an estimated 8,000 MIPS years. Sieving yielded about 900, 000 relations
involving about 760, 000 columns. After one day of structured Gaussian elimination,
following [31]), the matrix was reduced to size 484, 603 × 484, 603. The linear algebra isstill under way, using the improvement [37] of the block Wiedemann algorithm [6, 43].
Comparing both methods seems to suggest that the output of the sieving is betterwith the implementation [22] of the function field sieve, than with the implementation [36] of Coppersmith’s algorithm. We mentioned that Coppersmith’s algorithm
could be viewed as a special case of the function field sieve. In Coppersmith’s algor
rithm, one requires C(X) and C(X)2 to be simultaneously smooth. Without going
into mathematical details at this point, we briefly mention that this corresponds to the
choice of a polynomial of degree 2r in the function field sieve. However, such degree 2r
may not be optimal compared to other choices, which are not a power of 2. Theoretical analysis actually suggests that the optimal degree should be (n log n)1/3 . Since thefunction field sieve allows for any degree in selecting the polynomial, an appropriate
implementation may be faster than Coppersmith’s algorithm. Adleman already had
mentioned in [1] that it should be possible to optimize and specialize the function fieldsieve in F2n and achieve a better running time than Coppersmith’s algorithm. Besides,
sieving tricks used in the number field sieve can be applied to the function field sieve,and not to Coppersmith’s algorithm. It is therefore quite plausible that the methodof [22] can be extended to larger fields, thus beating the performances of [36].

4Consequences in terms of key sizes

4.1

The current status of the DLP

4.1.1

Prime fields

Surprisingly, it is very difficult to precisely estimate what is the largest size that current techniques for solving the DLP over prime fields could reach. The theoreticalcomplexity Lp [1/3; c + o(1)], c ≈ 1.92, is a rough estimate, which is not of much use.
Due to memory constraints, the size of the factor has to be kept significantly smaller
than the optimal choice that theory would dictate.
This is in contrast with the situation of factoring. The largest factorization with the
NFS factoring algorithm is a 512-bit RSA number [3] and this figure gives an accurate
account of what factoring algorithms can achieve. Practical experience with the NFS
method for the discrete logarithm appears more limited and the records are way behind.
10The current record [21] only tackles a 120-digit prime field, which corresponds to bitlength 397. However, in [26], the authors state that
It is generally accepted that, for any b in the current range of interest,
factoring b-bit integers takes about the same amount of time as computing
the discrete logarithm in b − x-bit field, where x is a small constant around
20.
This opinion may stem from the observation that the heuristic theoretical complexityof the NFS algorithms is the same for factoring and the DLP. Observe that the gap
between records does not lead to a fair comparison: the computing power used in [21]is an order of magnitude below what [3] required. Still, it is conceivable that the gap
is somehow larger than anticipated in [26]. Despite their similarities, there are several
technical differences between the two NFS algorithms.
• The polynomial selection differs. For instance [23] used the fact that one canefficiently solve polynomial equations over a finite field, which has no equivalent
in the setting of factoring. Different polynomial selections lead to different sieving
regions and different choices of factor bases.
• The sieving also slightly differs. In the factorization setting, the linear algebra isover F2 . This allows to use, besides the factor base, one or more so-called large
primes.
• The linear algebra differs. In the factorization setting, the matrix is binary,
whereas in the discrete logarithm setting, the matrix elements are integers modulo
p − 1. This limits drastically the size of the factor base.
4.1.2

Fields of characteristic 2

It is equally difficult to precisely estimate what is the largest size that current techniques
for solving the DLP over binary fields could reach. Again, the heuristic complexity
Lq [1/3; c + o(1)], where c ≈ 1.4 for Coppersmith’s algorithm, does not help much.
Besides having lower complexity than NFS, Coppersmith’s algorithm is much simpler toimplement. Implementing the function field sieve is almost as difficult as implementing
the number field sieve. However, because factoring polynomials over finite fields iseasy, sieving can be done more efficiently in the function field sieve than in the number
field sieve. Therefore, the function field sieve should be faster in practice than thenumber field sieve. Based on the above observations, it is no surprise that the tworecords in characteristic two are considerably larger than in the case of prime fields:
F2607 and F2521 . As noted in section 3.4.2, the former figure corresponds to a large
scale experiment based on Copermsmith’s algorithm, while the latter, based on thefunction field sieve, uses limited computing power, which leaves room for considerable
improvement.
11

4.2

Selecting key sizes

In practical situations, the sizes of cryptographic keys based on the DLP have to bechosen so that they outreach the expected performances of the algorithms for solving
the DLP, during the entire lifetime of the system. This involves making predictions.
In [3], the authors derive the following formulaY = 13.24D1/3 + 1928.6
for predicting the calendar year for factoring D-digit number by NFS. Following theopinion stated in [26], that the DLP in prime fields is 20 bits behind, which is apparently
a conservative estimate, we obtainY = 13.24(D + 6)1/3 + 1928.6
for predicting the calendar year for the discrete logarithm. Applying the formulawith D = 309, i.e. for a 1024 bit modulus, produces Y = 2019. Similarly, one gets
Y = 2042 for 2048-bit integers and Y = 2070 for 4096-bit. Thus, current key sizes forcryptosystems appear safe. Although no similar formula has been proposed for fields
of characteristic 2, it is advisable, based on the observations from section, to adopt key
sizes that are much larger.

References[1] L. M. Adleman. The function field sieve, Proc. ANTS-I, LNCS 877, SpringerVerlag, 108–121, 1994.
[2] M. Bellare and P. Rogaway. Random Oracles Are Practical: a Paradigm for
Designing Efficient Protocols, Proc. 1st CCS, 62–73, ACM Press, New York,1993.
[3] S. Cavallar, B. Dodson, A. K. Lenstra, W. Lioen, P. L. Montgomery, B. Murphy, H. te Riele, K. Aardal, J. Gilchrist, G. Guillerm, P. Leyland, J. Marchand,
F. Morain, A. Muffett, C. Putnam, C. Putnam, and P. Zimmermann. Factorizationof 512-bit RSA modulus, Proc. Eurocrypt ’00, LNCS 1807, 1–18, Springer-Verlag,
2000.
[4] Certicom. Information on the Certicom ECC challenge,
http://www.certicom.com/research/ecc challenge.html[5] D. Coppersmith. Fast evaluation of logarithms in fields of characteristic two IEEE
Trans. Inform. Theory, 30(4):587–594, 1984.

12

[6] D. Coppersmith. Solving linear equations over GF(2) via block Wiedemann algorithm, Math. Comp., 62:333–350, 1994.
[7] D. Coppersmith, A.M. Odlyzko and R.Schroeppel. Discrete Logarithms in GF(p),Algorithmica 1, 1–15, 1986.
[8] R. Cramer and V. Shoup. A practical public key cryptosystem provably secureagainst adaptive chosen ciphertext attack, Proc. Crypto’98, LNCS 1462, 13–25,
1998.
[9] Proposed federal Information Processing Standard for Digital Signature Standard,Federal Register, v.57, n.21, 3747–3749.
[10] T. El Gamal. A public key crtyptosystem and signature scheme based on discrete
logarithms, IEEE Trans. on Inform. theory, 469–472, 1985.
[11] A. Fiat and A. Shamir. How to Prove Yourself: Practical Solutions of Identificationand Signature Problems, Proc. Crypto ’86, LNCS 263, 186–194, Springer-Verlag,
Berlin, 1987.
[12] G. Frey, M. Müller, and H. G. Rück. The Tate-Pairing and the Discrete Logarithm
Applied to Elliptic Curve Cryptosystems, IEEE Trans. Inform. Theory, 45:1717–
1719, 1999.
[13] G. Frey and H. G. Rück. A Remark Concerning m-Divisibility and the Discrete
Logarithm in the Divisor Class Group of Curves, Math. Comp., 62:865–874, 1994.
[14] G.H. Golub and C.F. van Loan. Matrix computations, The John Hopkins University Press, 1989.
[15] D. Gordon and K. S. McCurley. Massively parallel computation of discrete logarithms, Proc. Crypto ’92, LNCS 740, 312–323, Springer-Verlag, 1993.
[16] D. M. Gordon. Discrete logarithms in GF(p) using the number field sieve, SIAM
J. Discrete Math., 6(1):124–138, 1993.
[17] R. Harley, D. Doligez, D. de Rauglaudre, X. Leroy, Elliptic Curve Discrete Logarithms: ECC2K-108,
http://cristal.inria.fr/ harley/ecdl7/[18] A. Hildebrand and G. Tenenbaum. Integers without large prime factors, J. Théor.
Nombres Bordeaux, (5):411–484, 1993.
[19] A. Joux and R. Lercier. Computing a discrete logarithm in GF (p), p a 90 digit
prime,
http://www.medicis.polytechnique.fr/ lercier/english/dlog.html
13

[20] A. Joux and R. Lercier. Computing a discrete logarithm in GF (p), p a 100 digit
prime,
http://www.medicis.polytechnique.fr/ lercier/english/dlog.html[21] A. Joux and R. Lercier. Computing a discrete logarithm in GF (p), p a 120 digits
prime
http://www.medicis.polytechnique.fr/ lercier/english/dlog.html[22] A. Joux and R. Lercier. Computing a discrete logarithm in GF (2521
http://www.medicis.polytechnique.fr/ lercier/english/dlog.html[23] A. Joux and R. Lercier. Improvements to the general number field sieve for discrete
logarithms in prime fields, Math. Comp., 2001, to appear.
[24] B. A. Lamacchia and A. M. Odlyzko. Computation of discrete logarithm in prime
fields, Designs, Codes and Cryptography, (1):47–62, 1991.
[25] A. K. Lenstra and H. W. Lenstra, Jr. The Development of the Number Field Sieve,
Lecture Notes in Mathematics 1554, Springer-Verlag, 1993.
[26] A.K. Lenstra and E. Verheul. Selecting cryptographic key sizes, PKC’2000, LNCS
1751, 446–465, 2000.
[27] A. Odlyzko. Discrete logarithms: The past and the future, Designs, Codes andCryptography, 19:129–145, 2000.
[28] D. Panario, X. Gourdon, and P. Flajolet. An analytic approach to smooth polynomials over finite fields, Algorithmic Number Theory – Proc. ANTS-III, LNCS
1423, Springer-Verlag, 1998.
[29] S. Pohlig and M. Hellman. An improved algorithm for computing logarithms overGF (p) and its cryptographic significance, IEEE Trans. Inform. Theory, 24, 106–
110, 1978.
[30] J. Pollard. Monte Carlo methods for index computation mod p, Math. Comp., 32,
918–924, 1978.
[31] C. Pomerance and J. W. Smith. Reduction of huge, sparse matrices over finite
fields via created catastrophes, Experiment. Math., 1(2):89–94, 1992.
[32] O. Schirokauer. Discrete logarithms and local units, Philos. Trans. Roy. Soc.
London Ser., A 345(1676):409–423, 1993.
[33] O. Schirokauer. Using number fields to compute logarithms in finite fields, Math.
Comp., 69(231):1627–283, 2000.
14

[34] O. Schirokauer, D. Weber, and T. Denny. Discrete logarithms: The effectivenessof the index calculus method, Proc. ANTS-II, LNCS 1122, Springer-Verlag, 1996.
[35] V. Shoup and T. Schweinberger. ACE Encrypt: The Advanced Cryptographic
Engine’ public key encryption scheme, Manuscript, March 2000. Revised, August
14, 2000.
[36] E. Thomé. Computation of discrete logarithms in F2607 , Proc. Asiacrypt ’01,
LNCS, to appear.
[37] E. Thomé. Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm, Proc. ISSAC ’01. ACM Press, 2001.
[38] P.C. van Oorschot and M. J. Wiener. Parallel collision search with cryptanalytic
applications, J. Cryptology, 12, (1999), 1–28.
[39] D. Weber. An implementation of the number field sieve to compute discrete
logarithms mod p, Proc. Eurocrypt ’95, LNCS 921, 95–105, Springer-Verlag, 1995.
[40] D. Weber. Computing discrete logarithms with the general number field sieve,
Proc. ANTS-II, LNCS 1122, Springer-Verlag, 1996.
[41] D. Weber and T. Denny. The solution of McCurley’s discrete log challenge, Proc.
Crypto ’98, LNCS 1462,458–471, Springer-Verlag, 1998.
[42] D. Weber, T. F. Denny and J. Zayer.
http://felix.unife.it/Root/d-Mathematics/d-Number-theory/t-Weber-discrete-logarithm-record-960925[43] D. H. Wiedemann. Solving sparse linear equations over finite fields, IEEE Trans.
Inform. Theory, 32:54–62, 1986.

15