.PH ""
.EQ
delim $$
define Run % bold R %
define vun % bold v %
.EN
.ds HP 10 10 10 10 10 10 10
.nr Df 2
.nr Pt 1
.nr Au 0
.am DE
.sp
.ls 2
..
.ce 99
.B
Discrete logarithms in finite fields and their cryptographic significance
.R
.sp
.I
A. M. Odlyzko
.R
.sp
AT&T Bell Laboratories
Murray Hill, New Jersey 07974
.sp 2
.I
ABSTRACT
.ce 0
.R
.sp
.P
Given a primitive element
$g$ of a finite field $GF (q)$,
the discrete logarithm of
a nonzero element
$u~member~GF (q)$ is that
integer $k$,
$1~<=~k~<=~q-1$, for which
$u~=~g sup k$.
The well-known problem of computing discrete
logarithms in finite fields has
acquired additional importance in
recent years due to its applicability
in cryptography.
Several cryptographic systems would become
insecure if an efficient discrete logarithm
algorithm were discovered.
This paper surveys and analyzes known algorithms
in this area, with special attention devoted
to algorithms for the fields
$GF ( 2 sup n )$.
It appears that in order to be safe from
attacks using these algorithms, the value
of $n$ for which $GF( 2 sup n )$ is used
in a cryptosystem has to be very
large and carefully chosen.
Due in large part to
recent discoveries, discrete logarithms
in fields $GF ( 2 sup n )$ are
much easier to compute than in
fields $GF(p)$ with $p$ prime.
Hence the fields $GF ( 2 sup n )$ ought to be
avoided in all cryptographic applications.
On the other hand, the fields $GF (p)$ with
$p$ prime appear to offer relatively high
levels of security.
.bp
.ce 99
.B
Discrete logarithms in finite fields and their cryptographic significance
.R
.sp
.I
A. M. Odlyzko
.R
.sp
AT&T Bell Laboratories
Murray Hill, New Jersey 07974
.sp
.ce 0
.ls 2
.H 1 Introduction
The multiplicative subgroup of any finite
field $GF (q)$, $q$ a prime power, is
cyclic, and the elements
$g~member~GF ( q )$ that generate this
subgroup are referred to as
.ul
primitive elements.
.PH "''- \\\\nP -''"
.nr P 1
Given a primitive element
$g~member~GF (q)$ and any
$u~member~GF ( q )*~=~GF ( q) - "{" 0 "}"$,
the
.ul
discrete logarithm
of $u$ with respect to $g$ is that integer
$k$, $0~<=~k~<=~q-1$, for which
.DS 2
.EQ
u~=~g sup k~.
.EN
.DE
We will write $k ~=~ log sub g ^ u$.
The discrete logarithm of $u$ is sometimes referred
to as the index of $u$.
.P
Aside from the intrinsic interest that the
problem of computing discrete logarithms
has, it is of considerable importance in
cryptography.
An efficient algorithm for discrete logarithms
would make several authentication and key-exchange
systems insecure.
This paper briefly surveys (in Section\ 2) these cryptosystems,
and then analyzes the known algorithms for
computing discrete logarithms.
As it turns out, some of them, including the
most powerful general purpose algorithm in
this area, have not been analyzed in complete
detail before.
Moreover, some of the analyses in the literature
deal only with fields $GF (p)$, where $p$ is a prime.
In cryptographic applications, on the other hand,
attention has been focused on the fields
$GF ( 2 sup n )$, since arithmetic in them is
much easier to implement, with respect to both
software and hardware.
Therefore we concentrate on the fields $GF ( 2 sup n )$.
.P
Several proposed algorithms for computing
discrete logarithms
are known.
We briefly discuss most of them (including some
unsuccessful ones) in Section 3.
In Section 4 we present the most powerful general
purpose algorithm that is known today, called the index-calculus algorithm, and analyze
its asymptotic performance.
Recently a dramatic improvement
in its performance in fields $GF(2 sup n )$ was made by
Coppersmith [18,19], and we discuss it in detail.
In Section 5 we discuss several technical issues that
are important to the performance of the index-calculus
algorithm, such as rapid methods to solve the systems
of linear equations that arise in it.
In that section we also
present several suggested
modifications to the Coppersmith algorithm which appear to be unimportant
asymptotically, but are of
substantial importance in practice.
We discuss them in order to obtain
a reasonable estimate of how fast
this algorithm could be made to
run in practice.
In Section 6 we estimate the
running time of that algorithm
for fields $GF (2 sup n )$ that might actually
be used in cryptography.
In Section 7 we briefly
discuss the performance
of the index-calculus algorithms in
fields $GF (p)$ for $p$ a prime.
Finally, we discuss the implications of these
algorithms for cryptography in Section 8.
It turns out, for example, that the MITRE scheme [38,59]
and the Hewlett-Packard chip [69], both of which use
the field $GF ( 2 sup 127 )$, are very insecure.
Depending on the level of security
that is desired, it seems that
fields $GF ( 2 sup n )$
to be used ought to have $n$ large,
no smaller than 800 and preferably
at least 1500.
Furthermore, these values of $n$
have to be very carefully chosen.
On the other hand, it appears
at this moment that the fields
$GF (p)$, where $p$ is a prime,
offer a much higher level of
security, with $p~>wig~2 sup 500$
adequate for many applications
and $p~>wig~2 sup 1000$ being
sufficient even for extreme situations.
The fields $GF(p)$ appear at this moment to offer security
comparable to that of the RSA scheme with modulus of size $p$.
.P
It has to be stressed that this survey presents the current state
of the art of computing discrete logarithms.
Since the state of the art has been advancing very rapidly recently,
this paper has already gone through several revisions.
The most important of the new developments has certainly been
the Coppersmith breakthrough in fields $GF ( 2 sup n )$.
Even more recently, there has been much less spectacular but
still important progress in fields $GF(p)$, which is briefly described
in Section 7, and in methods for dealing with sparse systems
of equations, which are discussed in Section 5, and which are
crucial for the index-calculus algorithms.
It is quite likely that further progress will take place in
discrete logarithm algorithms and so the cryptographic schemes
described below will require the use of even larger fields than
are being recommended right now.
.H 1 "Cryptographic systems related to discrete logarithms"
.P
One of the first published cryptosystems whose
security depends on discrete logarithms being
difficult to compute appears to be an authentication
scheme.
In many computer systems, users' passwords are
stored in a special file, which has the disadvantage
that anyone who gets access to that file is
able to freely impersonate any
legitimate user.
Therefore that file
has to be specially protected by the operating system.
It has been known for a long time (cf. [54]) that
one can eliminate the need for any secrecy by
eliminating the storage of passwords themselves.
Instead, one utilizes a function
$f$ that is hard to invert
(i.e., such that given a $y$ in the range of $f$,
it is hard to find an $x$ in the domain of $f$
such that $f(x)~=~y$) and creates a file containing
pairs $(i,~f(p sub i ) )$, where $i$ denotes a
user's login name and $p sub i$ the password of
that user.
This file can then be made public.
The security of this scheme clearly depends
on the function $f$ being hard to invert.
One early candidate for such a function was
discrete exponentiation; a field $GF (q)$
and a primitive element $g~member~GF (q)$
are chosen (and made public), and for $x$
an integer, one defines
.DS 2
.EQ
f(x)~=~g sup x~.
.EN
.DE
Anyone trying to get access to a computer while
pretending to be user $i$ would have to find
$p sub i$ knowing only the value of $g sup {p sub i}$;
i.e., he would have to solve the discrete logarithm
problem in the field $GF (q)$.
.P
Public key cryptography suffers from the defect that the
systems that seem safe are rather slow.
This disadvantage can be overcome to a large extent by
using a public key cryptosystem only to distribute
keys for a classical cryptosystem, which can then be
used to transmit data at high speeds.
Diffie and Hellman [23] have invented a key-exchange
system based on exponentiation in finite fields.
(This apparently was the very first public key cryptosystem
that was proposed.)
In it, a finite field $GF(q)$ and a primitive
element $g~member~GF(q)$ are chosen and made public.
Users $A$ and $B$, who wish to communicate using some
standard encryption method, such as DES, but who
do not have a common key for that system, choose
random integers $a$ and $b$, respectively, with
$2~<=~a,~b~<=~q-2$.
Then user $A$ transmits
$g sup a$ to $B$ over a public channel, while user $B$
transmits $g sup b$ to $A$.
The common key is then taken to be $g sup ab$,
which $A$ can compute by raising the received
$g sup b$ to the $a$ power (which only he knows),
and which $B$ forms by raising $g sup a$ to the
$b$ power.
It is clear that an efficient discrete logarithm
algorithm would make this scheme insecure, since
the publicly transmitted $g sup a$ would enable
the cryptanalyst to determine $a$, and he could then
determine the key used by $A$ and $B$.
Diffie and Hellman [23] have even conjectured that breaking
their scheme is equivalent in difficulty to computing
discrete logarithms.
This conjecture remains unproved, and
so we cannot exclude the possibility that there
might be some way to generate $g sup ab$ from
knowledge of $g sup a$ and $g sup b$ only, without
computing either $a$ or $b$,
although it seems unlikely that such a method exists.
.P
The Diffie-Hellman key-exchange scheme seems very
attractive, and it has actually been implemented
in several systems, such as a MITRE Corp. system [38,59].
Moreover, Hewlett-Packard has built a special
purpose VLSI chip which implements this scheme [69].
However, these implementations have turned out to be
easily breakable.
It appears possible, though, to build a Diffie - Hellman
scheme that is about as secure as an RSA scheme of comparable
key size.
This will be discussed at some length in Section\ 8.
.P
Systems that use exponentiation in finite fields to
transmit information have also been proposed.
One is based on an idea due to Shamir\ [37; pp. 345-346]
and has been advocated in the context of discrete
exponentiation by Massey and Omura\ [63].
For example, suppose user $A$ wishes to send a message
$m$ (which we may regard as a nonzero element of
the publicly known field $GF (q)$) to user $B$.
Then $A$ chooses a random integer $c$,
$1~<=~c~<=~q-1$,
$(c,q-1)~=~1$, and transmits $x~=~m sup c$ to $B$.
User $B$ then chooses a random integer $d$,
$1~<=~d~<=~q-1$,
$(d,q-1)~=~1$, and transmits $y=x sup d~=~m sup cd$
to $A$.
User $A$ now forms $z~=~y sup {c prime}$ where
$cc prime~==~1~( roman mod ~q-1)$, and transmits $z$
to $B$.
Since
.DS 2
.EQ
z~=~y sup {c prime}~=~m sup {cdc prime}~=~m sup d~,
.EN
.DE
$B$ only has to compute $z sup {d prime}$ to recover
$m$, where $dd prime~==~1~( roman mod~q-1)$, since
.DS 2
.EQ
z sup {d prime}~=~
m sup {dd prime}~=~m~.
.EN
.DE
In this scheme it is again clear that an efficient
method for computing discrete logarithms over $GF (q)$
would enable a cryptanalyst to recover the plaintext
message $m$ from the transmitted ciphertext messages
$m sup c$,
$m sup cd$, and $m sup d$.
.P
Another scheme for transmission of information has
been proposed by T. ElGamal\ [26] and is in essence
a variant of the Diffie-Hellman key distribution scheme.
User A publishes a public key $g sup a ~member~ GF(q)$,
where the field $GF(q)$ and a primitive root $g$ are
known (either they are also published by A or else
they are used by everyone in a given system), but
keeps $a$ secret.
User B, who wishes to send $m ~member~ GF(q)$ to A,
selects $k$ at random, $1 ^ <= ^ k ^ <= ^ q-2$ (a
different $k$ has to be chosen for each $m$)
and transmits the pair ($g sup k , ^ mg sup ak$) to A.
User A knows $a$ and therefore can compute
$g sup ak ~=~ (g sup k ) sup a$ and recover $m$.
An efficient discrete logarithm algorithm would
enable a cryptanalyst to compute either $a$ or $k$,
and would therefore make this scheme insecure also.
.P
T. ElGamal\ [26] has also proposed a novel
signature scheme that uses exponentiation in fields
$GF (p)$, $p$ a prime.
User A, who wishes to sign messages electronically,
publishes a prime $p$, a primitive root $g$ modulo
$p$, and an integer $y , ~1 <= y <= p-1$, which is
generated by choosing a random integer $a$, which
is kept secret, and setting $y ~=~ g sup a$.
(The prime $p$ and the primitive root $g$ can be
the same for all the users of the system, in which
case only $y$ is special to user A.)
To sign a message $m$, $1 ~<=~ m ~<=~ p-1$, user A
provides a pair of integers $(r,s)$, $1 ~<=~ r,s ~<=~ p-1$,
such that
.DS 2
.EQ (2.1)
g sup m ~==~ y sup r ~r sup s ~~~( {roman mod} ~p) ^.
.EN
.DE
To generate $r$ and $s$, user A chooses a random integer
$k$ with $(k, p-1) ~=~ 1$ and computes
.DS 2
.EQ
r ~=~ g sup k ^.
.EN
.DE
Since $y ~=~ g sup a$, this means that $s$ has to satisfy
.DS 2
.EQ (2.2)
g sup m ~==~ g sup {a r ~+~ ks} ~~~( {roman mod} ~p) ^,
.EN
.DE
which is equivalent to
.DS 2
.EQ (2.3)
m ~==~ ar ~+~ ks ~~~( {roman mod} ~p-1) ^.
.EN
.DE
Since $(k, ~p-1) ~=~ 1$, there is a unique solution
to (2.3) modulo $p-1$, and this solution is easy to find for
user A, who knows $a$, $r$, and $k$.
An efficient discrete logarithm algorithm would make
this scheme insecure, since it would enable the
cryptanalyst to compute $a$ from $y$.
No way has been found for breaking this scheme without
the ability to compute discrete logarithms, and so the
scheme appears quite attractive.
It is not as fast as the Ong-Schnorr-Shamir signature
scheme\ [50], but since several versions of that scheme
were recently broken by Pollard, it should not
be considered for use at the present time.
The ElGamal scheme appears to be about as secure
as the RSA scheme for moduli of the same length, as we
will see later, although it does expand bandwidth,
with the signature being twice as long as the message.
.P
The presumed intractability of the discrete logarithm problem
is crucial also for the Blum-Micali construction\ [9] of
a cryptographically strong random number generator.
What they show is that it is possible to compute a long
sequence that is obtained deterministically from a short
random sequence, and in which successive bits cannot be predicted
efficiently from the preceding ones without the ability
to compute discrete logarithms efficiently.
.P
A scheme whose security is essentially equivalent to that of
the Diffie - Hellman scheme was recently published by Odoni,
Varadharajan, and Sanders [49].
These authors proposed taking a matrix $B$ over $GF(p)$ which
is the companion matrix of an irreducible polynomial $f(x)$
of degree $m$ over $GF(p)$.
The Diffie - Hellman scheme would then be implemented by replacing
the primitive element $g$ by the matrix $B$, so that pairs of
users would transmit matrices $B sup a$ and $B sup b$ to each
other, where $a$ and $b$ are the two random integers chosen by
the two users.
However, the matrix ring generated by $B$ is isomorphic to the
field $GF ( p sup m )$, so this scheme does not provide any
additional security.
The more sophisticated scheme proposed in [49], with the matrix
$B$ being obtained from several companion matrices of
irreducible polynomials of degrees $m sub 1 ^,...,^ m sub s$ can
also be shown to be reducible to the problem of computing
discrete logarithms in the fields $GF ( p sup {m sub i} )$ separately.
.P
Finally, we mention that the ability to compute quantities
generalizing discrete logarithms in rings of integers
modulo composite integers would lead to efficient
integer factorization algorithms\ [5,40,45,52].
.H 1 "Some special algorithms"
In this section we discuss briefly some
algorithms that apparently don't work very well
and then we discuss a very useful
algorithm that works well only when all the prime
divisors of $q-1$ are of moderate size.
.P
The first method we discuss was not designed as
an algorithm at all.
In a field $GF (p)$, $p$ a prime, any function
from the field to itself can be represented as
a polynomial.
Wells\ [64] has shown that for any
$u$, $1 ~<=~ u ~<=~ p-1$, if $g$ is a primitive
root modulo $p$, then one can write
.DS 2
.EQ (3.1)
{roman log} sub g ~u~ ==~ sum from j=1 to p-2 ~(1 - g sup j ) sup -1
u sup j ~({roman mod} ~p) ^.
.EN
.DE
This formula is clearly useless computationally, but
it is interesting that such an explicit form for
the discrete logarithm function exists.
.P
The Herlestam-Johannesson method [32] was designed
to work over the fields $GF (2 sup n )$, and was
reported by those authors to work efficiently
for fields as large as $GF ( 2 sup 31 )$.
However, the heuristics used by those authors
in arguing that the method ought to work efficiently
in larger fields as well seem to be very questionable.
As usual, $GF (2 sup n )$ is represented as
polynomials over $GF (2) $ modulo some fixed
irreducible polynomial $f(x)$ of degree $n$
over $GF (2)$.
In order to compute the logarithm of $h(x)$ to base $x$,
Herlestam and Johannesson proposed to apply a
combination of the transformations
.DS 3
.EQ
h(x)~mark ->~
h(x) sup {2 sup r} ~,
.EN
.sp
.EQ
h( x)~lineup ->~
x sup {-2 sup s} h(x)
.EN
.DE
so as to minimize the Hamming weight
of the resulting polynomial, and apply
this procedure iteratively until
an element of low weight, for which
the logarithm was known, was reached.
There is no reason to expect such a strategy
to work, and considerable numerical evidence
has been collected which shows that this method
is not efficient [13,67],
and is not much better than a random walk
through the field.
However, some unusual phenomena
related to the algorithm have
been found whose significance
is not yet understood [13,57].
In particular, the algorithm does not always behave
like a random walk, and its performance appears to
depend on the choice of the polynomial defining the field.
These observations may be due to the small
size of the fields that were investigated, in
which case their significance would be slight.
.P
Another approach to computing
discrete logarithms in fields
$GF (2 sup n )$ was taken by
Arazi [3].
He noted that if one can determine
the parity of the discrete logarithm
of $u$, then one can quickly determine
the discrete logarithm itself.
Arazi showed that one can determine
the parity of discrete logarithms
to base $g$ fast if $g$ satisfies
some rather complicated conditions.
Since being able to compute discrete
logarithms to one base enables one
to compute them to any other base
about equally fast (as will be
discussed in Section 5), it would
suffice to find any $g$ that
satisfies Arazi's condition.
However, so far no algorithm has
been found for finding such
primitive elements
$g$ in large fields $GF ( 2 sup n )$,
nor even a proof that any such
elements exist.
It was shown by this author that
primitive elements $g$ satisfying
another set of conditions originally
proposed by Arazi, which were more
stringent than those of [3], do exist
in fields $GF( 2 sup n )$ for
$2~<=~n~<=~5$, but not for $6~<=~n~<=~9$.
Thus while the ideas of [3] are
interesting and may be useful in
future work, they appear to be of
little practical utility at this moment.
.P
We next discuss a very important algorithm
that was published by Pohlig and Hellman [51],
and whose earlier independent discovery they
credit to Roland Silver.
This algorithm computes discrete
logarithms over $GF ( q )$ using on the order
of $sqrt p$ operations and a comparable amount
of storage, where $p$ is the largest prime
factor of $q-1$.
In fact, there is a time-memory tradeoff that
can be exploited, and Pohlig and Hellman [51]
showed that if
.DS 2
.EQ (3.2)
q-1~=~
prod from i=1 to k~
p sub i sup n sub i~,
.EN
.DE
where the $p sub i$ are distinct
primes, and if $r sub 1 , "..." , r sub k$
are any real numbers with $0~<=~r sub i~<=~1$,
then logarithms over $GF (q)$ can be computed
in
.DS 2
.EQ
O( sum from i=1 to k~
n sub i ( log~q + p sub i sup {1-r sub i} (1+ log~p sub i sup
{r sub i} ) ) )
.EN
.DE
field operations, using
.DS 2
.EQ
O ( log~q ~ sum from i=1 to k~
(1+p sub i sup {r sub i } ) )
.EN
.DE
bits of memory, provided that a
precomputation requiring
.DS 2
.EQ
O ( sum from i=1 to k~
( p sub i sup {r sub i} log~p sub i sup {r sub i} +
log~ q ) )
.EN
.DE
field operations is carried out first.
.P
We now present a sketch of
the above algorithm.
Suppose that $g$ is some primitive element
of $GF (q)$, $x~member~GF (q) - "{" 0 "}"$,
and we wish to find an integer $a$,
$1~<=~a~<=~q-1$, such that
.DS 2
.EQ (3.3)
x~=~g sup a~.
.EN
.DE
Because of the Chinese Remainder Theorem,
we only need to determine $a$ modulo each
of the $p sub i sup {n sub i}$.
Suppose that $p~=~p sub i$ and $n~=~n sub i$
for some $i$.
Let
.DS 2
.EQ
a~==~
sum from j=0 to n-1~
b sub j p sup j ~~~( roman mod~ p sup n )~.
.EN
.DE
To determine $b sub 0$, we raise $x$ to the
$(q-1)/p$ power:
.DS 2
.EQ
y~=~
x sup {q-1 over p}~=~
g sup {a~q-1 over p}~=~
( q sup {q-1 over p} ) sup {b sub 0}~,
.EN
.DE
and note that $y$ is one of only $p$ elements, namely
.DS 2
.EQ
h sup 0~=~1 ,~h sup 1 ,~
h sup 2 , "..." , h sup p-1 ~,
.EN
.DE
where
.DS 2
.EQ
h~=~g sup (q-1)/p~.
.EN
.DE
How one determines $b sub 0$ we will describe below.
Once we have determined $b sub 0$, we can go on to
determine $b sub 1$ by forming
.DS 2
.EQ
(x g sup {-b sub 0 } ) sup {(q-1)/p sup 2}~=~
h sup {b sub 1} ~,
.EN
.DE
and so one.
.P
The value of $b sub 0$ is determined using
Shanks' "baby steps-giant steps" technique.
We are given $y$, and we need to find $m$ such
that $y~=~h sup m$, $0~<=~m~<=~p-1$.
If $r~member~Run$ is given, $0~<=~r~<=~1$,
we form
.DS 2
.EQ
u~=~\(lc p sup r \(rc~.
.EN
.DE
Then there exist integers $c$ and $d$ such that
.DS 2
.EQ
m~=~cu +d ,~~~
0~<=~d~<=~u-1 ,~~~
0~<=~c~<~p/u~.
.EN
.DE
Hence finding $m$ is equivalent to finding integers
$c$ and $d$ in the above ranges which satisfy
.DS 2
.EQ
h sup d~==~yh sup -cu~.
.EN
.DE
To find such $c$ and $d$, we can precompute $h sup d$
for $0~<=~d~<=~n-1$ and then sort the resulting values.
We then compute
$yh sup -cu$ for $c~=~0,1, "..."$, and check each
value for a match with the sorted table of values of $y sup d$.
The precomputation and sorting take
$O( p sup 2^ log~p )$ operations (note that these steps
have to be done only once for any given field), and there
are $O( p sup 1-r )$ values of $yh sup -cu$ to be computed.
.P
The Silver-Pohlig-Hellman algorithm is efficient whenever
all the prime factors of $q-1$ are reasonably
small.
(It is most efficient in fields in which $q$ is a
Fermat prime, $q~=~2 sup m +1$, for which there is
another polynomial-time discrete logarithm method
[41].)
Therefore great care has to be taken in selecting the
fields $GF( q )$ for use in cryptography.
This question will be discussed further in Section\ 8.
.P
We conclude this section by mentioning two interesting
randomized algorithms due to Pollard\ [52].
One of them computes discrete logarithms in fields $GF(q)$
in time roughly $q sup 1/2$.
The other algorithm finds the discrete logarithm of an
element in time roughly $w sup 1/2$, if that logarithm is
known to lie in an interval of size $w$.
.H 1 "A subexponential discrete logarithm method"
This section presents the fastest known general
purpose discrete logarithm method.
The basic ideas are due to Western and Miller [65]
(see also [47]).
The algorithm was invented independently
by Adleman [1], Merkle [46], and Pollard [52],
and its computational complexity
was partially analyzed by Adleman [1].
We will refer to it as the index-calculus algorithm.
Previous authors were concerned largely with the fields
$GF( p )$, where $p$ is a prime.
Here the method will be presented as it applies to
the fields $GF ( 2 sup n )$,
since they are of greatest
cryptographic interest.
An extensive asymptotic analysis
of the running time of the
algorithm in this and the related
cases $GF( p sup n )$ with $p$
fixed and $n~->~inf$ was given
recently by Hellman and
Reyneri [30].
As will be shown below, their
estimates substantially overestimate
the running time of this algorithm.
.P
Recently
some improvements on the index-calculus method
as it applies to the fields $GF (2 sup n )$
were made by I. Blake, R. Fuji-Hara, R. Mullin, and
S. Vanstone [8] which
make it much more efficient,
although these improvements
do not affect the asymptotics
of the running time.
Even more recently,
D. Coppersmith [18,19] has come
up with a dramatic improvement
on the $GF (2 sup n )$ version
of the algorithm (and more
generally on the $GF ( p sup n )$
version with $p$ fixed and
$n~->~inf$) which is much faster
and even has different asymptotic
behavior.
More recently, a whole series of improvements on the basic algorithm
have been discovered [20].
They do not approach the Coppersmith algorithm in asymptotic
performance, but they do apply to fields $GF(p)$ as well as
$GF(2 sup n )$ and they can be used to motivate Coppersmith's
algorithm (although they did not perform this function, having
come afterwards), so we briefly sketch them as well.
.P
The model of computation we will
assume in this section is that
of the Random Access Machine (RAM),
with no parallel computation.
In Section 6 we will
discuss what effect lifting this
restriction might have.
The index-calculus algorithm, at
least in the form presented here is
a probabilistic method in that the analysis of its running time
relies on assumptions about
randomness and independence of
various polynomials which seem
reasonable but at present cannot be proved.
.P
Before presenting the algorithm, it is necessary to
specify the notation that will be used.
As usual, we regard the field $GF ( 2 sup n )$ as
the ring of polynomials over $GF (2)$ modulo some
irreducible polynomial $f(x)$ of degree $n$.
Hence all elements $g~member~GF ( 2 sup n )$ can
be regarded as polynomials $g(x)$ over $GF (2)$
of degree $<~n$.
.P
One very important factor in analyzing the performance
of the index-calculus algorithm over $GF ( 2 sup n )$
is that polynomials over $GF (2)$ are very easy to
factor.
Algorithms are known [7,16,36,55] that can
factor $g(x)$
in time polynomial in the degree of $g(x)$.
Since the running time of the index-calculus
algorithm in $GF (2 sup n )$ is much higher (of the
form $exp (c ( n~log~n) sup 1/2 )$
for the basic version and of the form
$exp ( c prime n sup 1/3 ( log~n) sup 2/3 )$
for the Coppersmith version), we will
neglect the time needed to factor polynomials
in this section, since we will be concerned
here with asymptotic estimates.
In Section 6 we will perform a more
careful analysis for some specific
values of $n$.
.P
Suppose that $g(x)$, a polynomial of degree $<~n$
over $GF (2)$, is a primitive element of
$GF ( 2 sup n )$.
The index-calculus method for computing discrete
logarithms in $GF ( 2 sup n )$ with respect to the
base $g(x)$ consists of two stages.
The first stage, which is by far the more time and
space consuming, consists of the construction of
a large data base.
This stage only has to be carried out once for any
given field.
The second stage consists of the computation of the
desired discrete logarithms.
.P
We now present the basic version of the
index-calculus algorithm.
The initial preprocessing stage, which will be described
later, consists of the computation of the discrete
logarithms (with respect to $g(x)$) of a set $S$ of
chosen elements of $GF ( 2 sup n )$.
The set $S$ usually consists of all or almost all the irreducible
polynomials over $GF (2)$ of degrees $<=~m$, where $m$
is appropriately chosen.
Once the preprocessing stage is completed, logarithms
can be computed relatively rapidly.
The basic idea is that given $h~=~h(x)$,
to find $a~member~Z sup +$ such that
.DS 2
.EQ
h~==~g sup a ~~~( roman mod~f )~,
.EN
.DE
one chooses a random integer $s$,
$1~<=~s~<=~2 sup n -1$,
and computes
.DS 2
.EQ (4.1)
h*~==~h ~ g sup s
~~~( roman mod ~ f)~,~~~roman deg ~ h * ~<~n~.
.EN
.DE
The reduced polynomial $h*$ is then factored
into irreducible polynomials
and if all its factors are elements of $S$, so that
.DS 2
.EQ (4.2)
h * ~==~ h~g sup s~==~
prod from {v member S}~
v sup {b sub v ( h * )} ~~~( roman mod~ f)~,
.EN
.DE
then
.DS 2
.EQ (4.3)
log sub g ^ h~==~ sum from {v member S}
~b sub v ( h*) log sub g ^ v ~-~
s ~~~( roman mod ~ 2 sup n -1 )~.
.EN
.DE
.P
In the form in which we have presented
it so far, it is possible to obtain
a fully rigorous bound for the running time of the
second stage.
The
polynomials $h*$
in (4.1) behave like random polynomials over $GF (2)$
of degree $<~ n$.
Let $p(k,~m)$ denote the probability that a
polynomial over $GF(2)$ of degree exactly $k$
has all its irreducible factors of degrees $<=~m$;
i.e., if $N(k,m)$ is the number of polynomials
$w(x)~member~GF(2) [x]$ such that
$roman deg~ w(x)~=~k$ and
.DS 2
.EQ
w(x)~=~prod from i~
u sub i ( x ) sup {c sub i} ,~~~
roman deg~ u sub i ( x )~<=~m~,
.EN
.DE
then
.DS 2
.EQ (4.4)
p(k,m)~=~N(k,m) over N(k,k)~=~
N(k,m) over 2 sup k~.
.EN
.DE
We expect that if $S$
does consist of the irreducible
polynomials of degrees $<=~m$,
the reduced polynomial $h*$
in (4.1) will factor as in (4.2) with
probability approximately $p(n,m)$,
and that approximately $p(n,m) sup -1$
of the polynomials of the form (4.1)
will have to be generated before the
second stage of the algorithm succeeds
in finding the discrete logarithm of $h(x)$.
(This reasoning explains why the set $S$
is usually chosen to consist of all
irreducible polynomials of degrees $<=~m$
for some fixed $m$; any other set of
polynomials of equal cardinality is expected
to have a smaller chance of producing a
factorization of the form (4.2).)
.P
The function $p(n,m)$ can be evaluated fairly
easily both numerically and asymptotically.
Appendix A presents the basic recurrences
satisfied by $N(n,m)$ (from which
$p(n,m)$ follows immediately by (4.4)), and
shows that as $n~->~inf$ and $m~->~inf$ in
such a way that
$n sup 1/100~<=~m~<=~n sup 99/100$,
(which is the range of greatest
interest in the index calculus
algorithm),
.DS 2
.EQ (4.5)
p(n,m)~=~exp ( (1 + o (1) ) n over m ^ log sub e ^
m over n )~.
.EN
.DE
Appendix B consists of a table of $p(n,~m)$ for
a selection of values of $n$ and $m$,
which was computed using the recurrences in Appendix A.
Approximations better than that
of (4.5) for $p(n,m)$ can be obtained
with more work, but for practical
purposes the table of Appendix B is
likely to be quite adequate and is
more accurate to boot.
The analysis of Hellman and Reyneri [30]
relied on an estimate of $p(n,~m)$
that was essentially equivalent to
.DS 2
.EQ
p(n,~m) ~>=~
exp ( ( 1+o(1)) n over m~ log sub e ~
2e over n )~,
.EN
.DE
which while true, is much weaker than
(4.5).
.P
The polynomials $h *$ are always
of degree $<=~n-1$, and have degree
$n-k$ with probability $2 sup {- ^ k}$.
Hence the probability that $h*$
factors in the form (4.2) is
better approximated by
.DS 2
.EQ
sum from k=1 to n~
2 sup {-^ k} p(n-k,~m)~,
.EN
.DE
which is approximately
.DS 2
.EQ
p(n,~m)~
{(ne/m) sup 1/m} over {2- (ne/m) sup 1/m}~,
.EN
.DE
as follows from the results of Appendix A.
The last quantity above is $wig~p(n,~m)$
as $n~->~inf$,
$n sup 1/100 ~<=~m~<=~n sup 99/100$.
Hence
asymptotically this effect is
unimportant, although for small
values of $n$ and $m$ it can
make a difference; for example,
for $n~=~127$ and $m~=~17$
we obtain $1.51 p(127,~17)$
as the correct estimate of the
probability that $h *$ will
factor in the form (4.2).
.P
The relation (4.5) shows that the expected running time of
the second stage of the algorithm, as it has been
presented so far, is 
approximately
.DS 2
.EQ (4.6)
p(n,m) sup -1~=~ ( n over m ) sup {(1+o(1))n/m}~.
.EN
.DE
It was recently observed by Blake, Fuji-Hara,
Mullin, and Vanstone [8] that this stage can
be speeded up very substantially,
although at the cost of not being
able to provide an equally rigorous bound
for the running time.
Their idea is not to factor the polynomial
$h*$ defined by (4.1) directly, but instead
to find two polynomials $w sub 1$ and $w sub 2$
such that
.DS 2
.EQ (4.7)
h* ~==~ w sub 1 over w sub 2 ~~~ ( roman mod ~f)~,
.EN
.DE
and such that
$roman deg~ w sub i~<wig~n/2$ for $i~=~1,2$.
Once that is done, the $w sub i$ are factored,
and if each is divisible only by irreducibles
from $S$, say
.DS 2
.EQ (4.8)
w sub i~=~ prod from {v member S} ~ v sup {c sub v (i)}~,
.EN
.DE
then
.DS 2
.EQ (4.9)
log sub g ^ h~==~
sum from {v member S}
( c sub v (1)- c sub v (2) ) log sub g ^ v ~-~
s ~~~( roman mod~
2 sup n -1)~.
.EN
.DE
The advantage of this approach is that if the $w sub i$
behave like independently chosen random polynomials
of degree $wig~n/2$, as seems reasonable, then the
probability that both will factor into irreducibles
of degrees $<=~m$ is approximately $p ( [ n/2 ] , m ) sup 2$,
and therefore the expected number of polynomials $h*$ that
have to be tested is on the order of
.DS 2
.EQ (4.10)
p( [ n/2 ], m ) sup -2 ~=~
( n over 2m ) sup (1+o(1))n/m~.
.EN
.DE
This is smaller than the quality in (4.8) by
a factor of approximately $2 sup n/m$, and so
is very important, provided the $w sub i$
can be generated fast.
.P
The polynomials $w sub i$ can be generated very
rapidly (in time polynomial in $n$) by applying
the extended Euclidean algorithm [36,42] to $h*$
and $f$.
This algorithm produces polynomials $alpha$
and $beta$ over $GF(2)$ such that
$alpha h * ~+~beta f ~=~1$, the greatest
common divisor of $h*$ and $f$, and such that
$roman deg~alpha~<~roman deg~f~=~n$,
$roman deg~beta~<~roman deg ~h*~<~n$.
To do this, the algorithm actually computes a
sequence of triples of polynomials
$( alpha sub j , beta sub j , gamma sub j )$
such that
.DS 2
.EQ (4.11)
alpha sub j h * + beta sub j f~=~gamma sub j~,
.EN
.DE
where the final
$( alpha sub j , beta sub j , gamma sub j )~=~ ( alpha , beta , 1 )$,
$roman deg ~ gamma sub 1 ~>~roman deg ~ gamma sub 2 ~>~ "..."$,
and where
$roman deg~ alpha sub j~<=~n-1~-~ roman deg~ gamma sub j$.
If we choose that $j$ for which $roman deg~ gamma sub j$
is closest to $n/2$, then $w sub 1~=~gamma sub j$ and
$w sub 2~=~alpha sub j$ will satisfy the congruence (4.7),
and their degrees will be relatively close to $n/2$
most of the time.
These $w sub 1$ and $w sub 2$
are not completely independent
(for example, they have to be
relatively prime), but on the
other hand their degrees will
often be less than $n/2$, so
on balance it is not
unreasonable to expect that
the probability of both having
a factorization of the form
(4.8) should be close to
$p( [n/2] ,~m ) sup 2$.
.P
The above observations justify the claim that the
second stage of the index-calculus algorithm, as
modified by Blake et al., ought to take on the
order of $p( [n/2],m ) sup -2$ operations on
polynomials of degree $<=~n$ over
$GF ( 2)$, where each such polynomial operation
might involve on the order of $n sup 3$ bit
operations.
For small values of $n$,
$p( [n/2] , m )$ can be found in Appendix B,
while for very large $n$, the quantity on the
right side of (4.10) ought to be a reasonable
approximation to the running time of the second
stage.
.P
It is clear that the running time of the second stage
can be decreased by increasing $m$.
Doing that, however, increases both storage
requirements and the running time of the first
(preprocessing) stage of the algorithm.
It is well known (see Appendix A) that the
number of irreducible polynomials of degree
$<=~m$ is very close to $m sup -1 2 sup m+1$,
and for each one it is necessary to store
roughly $n$ bits, namely its logarithm (which
is in the range $[1, 2 sup n -1 ]$).
This already puts a limit on how large $m$
can be, but this limit is not very stringent,
since these discrete logarithms can be stored
on slow storage devices, such as tape.
This is due to the fact that they are needed
only once in the computation of each discrete
logarithm by stage two, when both of the
polynomials $w sub i$ are discovered to have
factorizations of the form (4.8).
Thus this argument does not exclude the use
of values of $m$ on the order of 40.
.P
A much more severe limitation on the size of $m$
and $n$ is placed by the preprocessing first stage,
which we now discuss.
The basic idea there is to choose a random
integer $s$, $1~<=~s~<=~2 sup n -1$,
form the polynomial
.DS 2
.EQ
h*~==~g sup s  ~~~( roman mod ~f),~~~
roman deg ~ h * ~<~n~,
.EN
.DE
and check whether $h*$ factors into irreducible
factors from $S$.
If it does, say
.DS 2
.EQ (4.12)
h*~=~prod from {v member S} ~ v sup {b sub v ( h*)}~,
.EN
.DE
then we obtain the congruence
.DS 2
.EQ (4.13)
s
~==~
sum from {v member S}~
b sub v ( h *) log sub g ~ v ~~~( roman mod~2 sup n -1 )~.
.EN
.DE
Once we obtain slightly more than $| S |$
such congruences, we expect that they will
determine the $log sub g ~ v$, $v member S$,
uniquely modulo $2 sup n -1$, and the first
stage will be completed.
There is a complication here in that $2 sup n -1$
is not in general a prime, so that solving the
system (4.13) might require working separately
modulo the different prime power divisors of
$2 sup n -1$
and using
the Chinese Remainder Theorem to reconstruct
the values of $log sub g ~ v$.
This complication is not very serious,
and if it does occur, it should lead
to a speedup in the performance of the
algorithm, since arithmetic would have
to be done on smaller numbers.
In any case this complication does not
arise when $2 sup n -1$ is a prime.
A general linear system of the form
(4.13)
for the $log sub g ~ v$ takes on the
order of $| S | sup 3$ steps to solve if we use straightforward gaussian
elimination.
(We neglect here multiplicative factors
on the order of $O(n sup 2 )$.)
This can be lowered to
$| S | sup r$ for $r~=~2.495548 "..."$
using known fast matrix multiplication algorithms [21],
but those are not practical for reasonably sized
$| S |$.
The use of Strassen's matrix multiplication
algorithm [10] might be practical for large $n$, and would lower
the running time to about
$| S | sup r$ with
$r~=~log sub 2 ~ 7~=~2.807 "..."~$.
However, the systems of linear equations that arise in the
index-calculus algorithms are quite special in that they are
quite sparse.
(i.e., there are only a few nonzero coefficients).
It was only recently discovered that this sparseness can be
effectively exploited, and systems (4.13) can be solved in
time essentially $| S | sup 2$.
This development will be described in Section 5.7.
.P
Generation of $| S |$ congruences of the form
(4.13) takes about
.DS 2
.EQ
| S | ~~p ( n,m) sup -1
.EN
.DE
steps if we use the algorithm as
described above.
If instead we use the Blake et al.
modification described in connection with
the second stage, in which instead of
factoring $h*$ right away, we first express
it in the form (4.7) with $roman deg~ w sub i ~<wig~n/2$,
$i~=~1,2$, and then factor the $w sub i$,
then generation of $| S |$ of the
congruences (4.13) ought to take on the order of
.DS 2
.EQ (4.14)
| S | ~~ p ( [ n/2 ] ,~ m ) sup -2
.EN
.DE
steps, where each step takes a polynomial
number (in $n$) of bit operations.
Thus the first stage of the algorithm takes on the order
of
.DS 2
.EQ (4.15)
| S |~~
p ( [n/2] ,~ m ) sup -2 ~+~
| S | sup 2
.EN
.DE
steps.
Hence using
our approximations to $p(k,~m)$
and $| S |$ and discarding polynomial
factors yields an estimate of the running
time of the form
.DS 2
.EQ (4.16)
2 sup m ( n over 2m ) sup n/m~+~2 sup {2 m}~.
.EN
.DE
(To be precise, the exponents in
(4.16) should be multiplied by
$1+o(1)$.)
The quantity
.DS 2
.EQ
2 sup m ( n over 2m ) sup n/m
.EN
.DE
is minimized approximately for
$m~wig~ c sub 1 ( n~log sub e n ) sup 1/2$,
where
.DS 2
.EQ
c sub 1~=~
(2~log sub e 2 ) sup -1/2~=~
0.8493 "..."~,
.EN
.DE
in which case
.DS 2
.EQ (4.17)
2 sup m ( n over 2m ) sup n/m~=~
exp ~
( ( c sub 2 + o(1)) ~ sqrt {n~log sub e ~n } ) ~~~roman as~~
n ~->~inf~,
.EN
.DE
where
.DS 2
.EQ
c sub 2~=~
c sub 1 ~log sub 2~2+ ( 2c sub 1 ) sup -1 ~=~
( 2 ~log sub e ~ 2 ) sup 1/2~=~1.1774 "..."~.
.EN
.DE
For $m ~wig~ c sub 1 (n ~ log sub e n ) sup 1/2 , ~~2 sup 2m$ is also
of the form (4.17), so the time to solve the system of linear
equations is of the same asymptotic form as the time needed to generate them.
.P
If we modify the notation used by
Pomerance [53] in his survey of
integer factorization and let $M~=~M(n)$
represent any quantity satisfying
.DS 2
.EQ
M~=~exp ( (1+o(1)) ~(n~log sub e ~ n) sup 1/2 ) ~~~
roman as~~ n~->~inf~,
.EN
.DE
then our analysis shows that the first
stage of the basic index-calculus algorithm
can be carried out in
time $M sup 1.178$.
.P
The time required by the second
stage of the index-calculus
algorithm to compute a single
discrete logarithm is
.DS 2
.EQ
M sup {(2c sub 1 ) sup -1} ~=~ M sup 0.588... ~.
.EN
.DE
This running time estimate is
much lower than for the first
stage.
The space requirements of the second
stage are essentially negligible.
It is necessary to have access to the
logarithms of the elements of $S$,
which requires
.DS 2
.EQ
exp~ ( ( c sub 1 ~ log sub e ~ 2 + o( 1)) ~
(n~log sub e ~n) sup 1/2 )
.EN
.DE
bits of storage,
but these logarithms are needed only
once, and so they can be stored on a
cheap slow-access device, such as tape.
.P
Our estimates for the running
time of the basic index-calculus algorithm
for the fields $GF( 2 sup n )$
are substantially smaller than
those of Hellman and Reyneri [30].
This is due primarily to our use
of a more accurate estimate for
$p(n,~m)$.
The Blake et al. innovation which
replaces the polynomial $h*$ by
the quotient of two polynomials, each
of roughly half the degree of
$h*$ turns out not to affect the
asymptotic estimate, since it
improves the running time only
by the factor $2 sup n/m$, which
is $M sup o(1)$ for $m~wig~c ( n~ log sub e ~n) sup 1/2$.
However, for values of $n$
that might be of practical
interest, say $200~<=~n~<=~1000$,
and best possible choices of $m$,
this factor $2 sup n/m$ is very
important, speeding up the
algorithm by between two and ten
orders of magnitude.
.P
We next describe several algorithms that improve on the asymptotic
performance of the basic index-calculus algorithm to an extent
greater than the Blake et al. [8] modification.
They are nowhere near as fast as the Coppersmith version, since
they still run in time $M sup c$ for some constant $c ~>~ 0$, but
they have the property that $c ~<~ c sub 2$.
They are presented here very briefly in order to show the
variety of methods that are available,
and also to motivate the Coppersmith algorithm.
Like the Coppersmith method, these variants depend on the
polynomial $f(x)$ that defines the field being of a somewhat
special form, namely
.DS 2
.EQ (4.18)
f(x)~=~x sup n ~+~ f sub 1 (x)~,
.EN
.DE
where the degree of $f sub 1 (x)$
is small.
Since approximately one polynomial of degree
$n$ out of $n$ is irreducible (cf. Appendix A), we can expect
to find $f(x)$ of the form (4.18)
with $roman deg~f sub 1 (x)~<wig~log sub 2~n$.
(The $f sub 1 (x)$ of smallest degrees for
which $x sup n ~+~ f sub 1 (x)$ is irreducible
for some interesting values of $n$ are
$f sub 1 (x)~=~x+1$ for
$n~=~127$,
$f sub 1 (x)~=~x sup 9 + x sup 6 + x sup 5 + x sup 3 +x+1$
for $n~=~521$,
$f sub 1 (x)~=~x sup 9 + x sup 7
+ x sup 6 + x sup 3 + x +1$
for $n~=~607$, and
$f sub 1 (x)~=~
x sup 11 + x sup 9 + x sup 8 +
x sup 5 + x sup 3 + x sup 2 + x +1$
for $n~=~1279$.)
As is explained in Section 5.2,
this is not a severe restriction,
since being able to compute logarithms
rapidly in one representation of a field
enables one to compute logarithms in any
other representation just about as fast.
.P
The first algorithm we discuss is one of several that have
the same asymptotic performance.
(The other algorithms in this group are described in [20], at
least in the form applicable to fields $GF(p)$.)
It is basically an adaptation of the Schroeppel factorization
algorithm [20,53].
We assume that $f(x)$ is of the form (4.18) with $roman deg ~f(x) ~<=~ n/2$,
say.
This time we let $S ~=~ S sub 1 ~cup~ S sub 2$, where $S sub 1$
consists of the irreducible polynomials of degrees $<= m$, and
$S sub 2$ of polynomials of the form
.DS 3
.EQ (4.19)
x sup k ~+~ g(x), ~~~ roman deg ~g(x) ~<=~ m ^,
.EN
.DE
where $k ~=~ left ceiling n/2 right ceiling$ is the least integer
$>= ~n/2$.
Consider any $h sub 1 (x) , ~h sub 2 (x) ~epsilon~ S sub 2$.
If
.DS 3
.EQ
h sub i (x) ~=~ x sup k ~+~ h tilde sub i (x), ~~~i =1,2 ^,
.EN
.DE
then, if we write $2k ~=~ n+a$, $a ~=~ 0$ or 1, we have
.DS 3
.EQ
h sub 1 (x) ~h sub 2 (x) ~mark =~ x sup 2k ~+~ x sup k ( h tilde sub 1 (x)
~+~ h tilde sub 2 (x)) ~+~ h tilde sub 1 (x) h tilde sub 2 (x)
.EN
.sp
.EQ (4.20)
~lineup =~ x sup a (f (x) ~+~ f sub 1 (x)) ~+~ x sup k ( h tilde sub 1
(x) + h tilde sub 2 (x)) ~+~ h tilde sub 1 (x) h tilde sub 2 (x)
.EN
.sp
.EQ
~lineup ==~ x sup k ( h tilde sub 1 (x) + h tilde sub 2 (x)) ~+~ h tilde
sub 1 (x) h tilde sub 2 (x) ~+~ x sup a f sub 1 (x) ~( roman mod ~f(x)) ^,
.EN
.DE
and so the polynomial on the right side of (4.20) is of degree
roughly $n/2$ (for $m ~=~ o(n)$, as will be the case).
If that polynomial, call it $h sup * (x)$, factors into irreducible
polynomials of degrees $<= m$, say
.DS 3
.EQ
h sup * (x) ~=~ prod from {v epsilon S sub 1} ~v(x) sup {b sub v ( h sup * )}
^,
.EN
.DE
then (4.20) yields a linear equation for the logarithms of the
elements of $S$:
.DS 3
.EQ (4.21)
log sub g ~h sub 1 ~+~ log sub g ~h sub 2 ~==~ sum from {v epsilon S sub 1}
~b sub v ( h sup * ) ~log sub g ~v ~~( roman mod ~2 sup n -1) ~.
.EN
.DE
Since each of $S sub 1$ and $S sub 2$ has on the order of $2 sup m$
elements, once we obtain about $2 sup m$ equation of the form (4.21),
we ought to be able to solve them and obtain the discrete logarithms
of the elements of $S sub 1$, which is what is desired.
Now there are approximately $2 sup 2m$ different pairs
$h sub 1 , h sub 2$ that can be tested, and if the $h sup *$
behave like random polynomials of degrees about $n/2$, each
will factor into irreducibles of degrees $<= m$ with probability
approximately $p( [n/2], ~m)$.
Hence we will have to perform about $2 sup 2m$ polynomial
time factorizations and obtain about $2 sup 2m ~p( [n/2], ~m)$
equations of the form (4.21).
Therefore we need
.DS 3
.EQ (4.22)
2 sup 2m ~p( [n/2], ~m) ~>wig~ 2 sup m ^,
.EN
.DE
and the work we do is on the order of $2 sup 2m$, since the
linear equations can also be solved in this much time.
To minimize the running time, we choose the smallest $m$
for which (4.22) is satisfied, and a brief computation shows
that the right choice is $m ~wig~ c sub 3 (n ~log sub e ~n ) sup 1/2$
as $n ~->~ inf$, with $c sub 3 ~=~ (4 ~log sub e ~ 2) sup {- 1/2}$,
so that the running time of the first stage of this algorithm is
.DS 3
.EQ (4.23)
M sup {c sub 4} ~=~ M sup 0.8325... ~~,~~ c sub 4 ~=~ ( log sub e ~2) sup 1/2 ~.
.EN
.DE
.P
The improvement in the exponent of $M$ is the running time estimate
of the first stage from 1.177... in the basic algorithm to 0.832...
in the version above was due to the fact that this time, in order
to obtain a linear equation we only had to wait for a single
polynomial of degree about $n/2$ to split into low degree irreducibles,
instead of a single polynomial of degree $n$ or two polynomials of
degree $n/2$.
In the next algorithm, we obtain a further improvement by reducing
to the problem of a single polynomial of degree about $n/3$ splitting
into low degree irreducibles.
The method is an adaptation of the so-called ``cubic sieve'' for
factoring integers, which was invented by J. Reyneri some years ago
and rediscovered independently several times since then (see [20]
for further details).
This time we assume that $f(x)$ has the form (4.18) with
$roman deg ~f sub 1 (x) ~<=~ n/3$.
We set $k ~=~ left ceiling n/3 right ceiling$ and let $S ~=~ S sub 1 ~cup~ S sub 2$
with $S sub 1$ consisting of the irreducible polynomials of
degrees $<= m$ and $S sub 2$ of polynomials of the form
$x sup k ~+~ h(x), ~~roman deg ~ h(x) ~<=~ m$.
We consider pairs $h sub 1 (x)$ and $h sub 2 (x)$ with each
$h sub i (x)$ of degree $<= m$, and let
.DS 3
.EQ (4.24)
h sup * (x) ~==~ ( x sup k + h sub 1 (x)) ~( x sup k + h sub 2 (x))
~( x sup k + h sub 1 (x) + h sub 2 (x)) ~~( roman mod ~f(x)) ^,
.EN
.DE
$0 ~<=~ roman deg ~ h sup * (x) ~<~ n$.
We then have
.DS 3
.EQ (4.25)
h sup * (x) ~==~ x sup 3k ~+~ x sup k ( h sub 1 sup 2 + h sub 1 h sub 2
+ h sub 2 sup 2 ) ~+~ h sub 1 h sub 2 ( h sub 1 + h sub 2 )~~( roman mod ~f) ^,
.EN
.DE
and since
.DS 3
.EQ
x sup 3k ~==~ x sup a f sub 1 (x) ~( roman mod ~f(x))
.EN
.DE
for some $a, ~0 ~<=~ a ~<=~ 2$, we find that $h sup * (x)$
is of degree about $k ~wig~ n/3$ if $m ~=~ o(n)$.
If $h sup * (x)$ is divisible only by irreducibles in
$S sub 1$, we obtain a linear equation relating logarithms
of three elements of $S sub 2$ to those of elements of $S sub 1$.
There are about $2 sup 2m$ pairs $h sub 1 (x), h sub 2 (x)$
to test, and so if the $h sup * (x)$ behave like random
polynomials of degrees $wig ~n/3$, we expect to obtain about
$2 sup 2m ~p( [n/3], ~m)$ equations.
Since there are about $2 sup m$ elements of $S$, we therefore
need to choose $m$ so that
.DS 3
.EQ (4.26)
2 sup 2m ~p( [n/3], ~m) ~>wig~ 2 sup m ~.
.EN
.DE
The time to run the algorithm is (within polynomial factors of $n$)
$2 sup 2m$, both to form and factor the polynomials $h sup * (x)$,
and to solve the system of linear equations.
A simple computation shows that the smallest $m$ that satisfies
(4.26) has $m ~wig~ c sub 5 (n ~ log sub e ~ n ) sup 1/2$, where
$c sub 5 ~=~ (6 ~ log sub e ~ 2 ) sup {- 1/2}$, and the running time
of the first phase of this algorithm is
.DS 3
.EQ (4.27)
M sup {c sub 6} ~=~ M sup 0.6797... ~~,~~ roman where ~c sub 6 ~=~ (2 ( log
sub e ~2)/3) sup 1/2 ~.
.EN
.DE
.P
The running times of the second phases of the two algorithms
presented above can be improved beyond what is obtained by
using the strategy of the basic variant, but we will not discuss
that subject.
Details can be found in [20], in the case of fields $GF( p)$, $p$
a prime, and it is easy to adapt those methods to the fields
$GF (2 sup n )$.
.P
The variants of the index-calculus algorithm presented above
raise the question of whether they can be generalized so as to
give even faster algorithms.
The obvious idea is to use more than three factors and choose
those factors in such a way that the product will reduce modulo
$f(x)$ to a polynomial of low degree.
A very clever way to do this was found by Coppersmith [18,19].
However, his work was motivated by different considerations.
.P
We next present the Coppersmith
variation [18,19] on the index-calculus
algorithm.
Unlike the basic algorithm,
which runs in time roughly of the form
$exp ( n sup 1/2 )$ in fields
$GF ( 2 sup n )$, this new variation
runs in time which is roughly of the
form $exp ( n sup 1/3 )$.
Unlike the basic version, though, the
Coppersmith variant does not apply to
the fields $GF (p)$ with $p$ prime.
Just like the algorithms presented above,
the Coppersmith algorithm relies on
several unproved assumptions.
Since these assumptions are supported by both heuristic
reasoning and empirical evidence, though, there seems
to be no reason to doubt the validity of the algorithm.
.P
The Coppersmith algorithm was inspired
to a large extent by the Blake et al. [8]
method of systematic equations, which is
explained in Section 5.1, and which yields
many linear equations involving logarithms
at very low cost.
Like the systematic equations method,
it depends on the polynomial $f(x)$
being of a the special form (4.18) with $f sub 1 (x)$ of very low degree.
.P
We now discuss the first stage of the
Coppersmith variant of the index-calculus
algorithm.
We assume that the field $GF ( 2 sup n )$
is defined by a polynomial $f(x)$ that
is of the form (4.18) with $roman deg~ f sub 1 (x)~<wig~ log sub 2 ~n$.
The first stage consists again of the
computation of logarithms of $v~member~S$,
where $S$ consists of irreducible polynomials
of degrees $<=~ m$, but now $m$ will be
much smaller, on the order of
$n sup 1/3 ( log sub e~ n ) sup 2/3$.
We will also assume that
$g(x)~member~S$, since it follows from Section 5.2
that this restriction does not affect the
running time of the algorithm.
.P
The essence of the Blake et al. [8]
improvement of the basic index-calculus
algorithm is that it replaced the
factorization of a single polynomial
of degree about $n$ by the factorization
of two polynomials of degrees about $n/2$
each.
The essence of the two improvements discussed above
was that they rely on the factorization of polynomials
of degrees about $n/2$ and $n/3$, respectively, into
low degree irreducibles.
The essence of the Coppersmith [18,19] improvement
is that it instead relies on factorization
of two polynomials of degrees on the order
of $n sup 2/3$ each.
The lower the degree of the polynomials being
factored, the greater the probability that they
will consist only of small degree irreducible
factors.
To accomplish this lowering of the degree,
take
$k~member~Z sup +$
($k$ will be chosen later so that $2 sup k$ is
on the order of $n sup 1/3 ( log sub e ~ n ) sup -1/3 $)
and define
.DS 2
.EQ (4.28)
h~=~ \(lf n ^ 2 sup -k \(rf ~+~1~.
.EN
.DE
Pick
$u sub 1 (x)$ and $u sub 2 (x)$ of
degrees $<=~B$ ($B$ will be chosen
later to be on the order of $n sup 1/3 ( log sub e ~ n ) sup 2/3 )$
with $( u sub 1 (x),~ u sub 2 (x) )~=~1$, and set
.DS 2
.EQ (4.29)
w sub 1 (x)~=~u sub 1 (x) x sup h ~+~
u sub 2 (x)~.
.EN
.DE
Next let
.DS 2
.EQ (4.30)
w sub 2 (x) ~==~
w sub 1 (x ) sup 2 sup k ~~~
( roman mod~ f(x) ) ~,~~~roman deg~
w sub 2 (x) ~<~ n~.
.EN
.DE
We then have
.DS 3
.EQ
w sub 2 (x) ~mark ==~
u sub 1 ( x sup 2 sup k ) x sup {h2 sup k} ~+~
u sub 2 ( x sup {2 sup k} ) ~~~( roman mod~ f (x ) )~,
.EN
.sp
.EQ (4.31)
lineup =~
u sub 1 ( x sup {2 sup k} ) x sup {h2 sup k -n} f sub 1 (x) ~+~
u sub 2 ( x sup {2 sup k } )~.
.EN
.DE
If $B$ and $2 sup k$ are on the order of $n sup 1/3$,
then $h$ is on the order of $n sup 2/3$,
$h ^ 2 sup k - n$ is on the order of $n sup 1/3$,
and so both $w sub 1 (x)$ and $w sub 2 (x)$
have degrees on the order of $n sup 2/3$.
Since
.DS 2
.EQ
log sub g ~ w sub 2 (x) ~==~
2 sup k ~ log sub g ~ w sub 1 (x) ~~~
( roman mod~ 2 sup n -1 )~,
.EN
.DE
if both $w sub 1 (x)$ and $w sub 2 (x)$
have all their irreducible factors in $S$
we obtain a linear equation for the
$log sub g ~ v $,
$v ~member~S$.
(The restriction
$(u sub 1 ( x),~ u sub 2 (x))~=~1$
serves to eliminate duplicate
equations, since the pairs
$u sub 1 (x),~ u sub 2 (x)$ and
$u sub 1 (x) t (x) ,~ u sub 2 (x) t (x)$
produce the same equations.)
.P
We next consider the Coppersmith algorithm
in greater detail.
We need to obtain about $| S |$ linear
equations for the $log sub g ~v$,
$v~member~S$.
Now
.DS 3
.EQ
roman deg~~ w sub 1 (x) ~mark <=~
B+h ~,
.EN
.sp
.EQ
roman deg~~
w sub 2 (x) ~lineup <=~
B ~cdot ~ 2 sup k ~+~ 2 sup k~+~ roman deg ~~ f sub 1 (x)~,
.EN
.DE
so
if $w sub 1 (x)$ and $w sub 2 (x)$
behave like independent random
polynomials of those degrees, then
the probability that both
$w sub 1 (x)$ and $w sub 2 (x)$
have all their irreducible factors
in $S$ is approximately
.DS 2
.EQ (4.32)
p ( B+h ,~ m ) p ( B2 sup k + 2 sup k ,~ m)
~.
.EN
.DE
Of course $w sub 1 (x)$ and $w sub 2 (x)$
are neither independent nor random.
However, as far as their factorizations
are concerned, it does not appear unreasonable
to expect that they will behave like
independent random polynomials, and this
does turn out to hold in the case $n~=~127$
studied by Coppersmith [18,19].
Therefore to obtain $| S |~wig~ m sup -1 2 sup m+1$
equations we need to satisfy
.DS 2
.EQ (4.33)
2 sup 2B ~ p ( B+h ,~ m ) p ( B2 sup k + 2 sup k ,~
m) ~>wig~ 2 sup m ~.
.EN
.DE
The work involved consists of generating
approximately $2 sup 2B$ polynomials $w sub 1 (x)$
and testing whether both $w sub 1 (x)$ and
$w sub 2 (x)$ have all their irreducible
factors in $S$.
Once these roughly $2 sup m$ equations
are generated, it becomes necessary to
solve them, which takes about $2 sup 2m$
operations.
The estimate (4.5) shows that to minimize
the running time, which is approximately
.DS 2
.EQ
2 sup 2B ~+~ 2 sup 2m~,
.EN
.DE
subject to (4.33), it is necessary to take
.DS 3
.EQ (4.34a)
2 sup k ~mark wig~ alpha ~ n sup 1/3 ~
( log sub e ~ n ) sup -1/3~,
.EN
.sp
.EQ (4.34b)
m~lineup wig~
beta ~ n sup 1/3 ~ ( log sub e ~ n) sup 2/3~,
.EN
.sp
.EQ (4.34c)
B~lineup wig~ gamma ~ n sup 1/3 ~
( log sub e ~ n ) sup 2/3~,
.EN
.DE
as $n~->~ inf$, where $alpha ,~ beta $,
and $gamma$ are bounded away
from both zero and infinity.
Under these conditions we find that the
running time of the first stage of the
algorithm is
.DS 2
.EQ (4.35)
K sup {2 gamma ~ log sub e ~ 2 } ~+~
K sup {2 beta ~ log sub e ~ 2 }~,
.EN
.DE
where $K~=~ K(n)$
denotes any quantity that satisfies
.DS 2
.EQ (4.36)
K~=~
exp ~ ( ( 1 + o(1) ) ~n sup 1/3 ~ ( log sub e ~n) sup 2/3 )~,
.EN
.DE
and this is subject to the condition
.DS 2
.EQ (4.37)
2~gamma~log sub e ~2~-~
1 over {3 alpha beta } ~-~
{alpha gamma} over {3 beta} ~>=~
( 1 + o( 1)) ) beta ~ log sub e ~ 2 ~.
.EN
.DE
Let us now regard $alpha ,~ beta $, and $gamma$
as continuous variables.
Since the estimate (4.35) does not depend on
$alpha$, we can choose $alpha$ freely.
The quantity on the left side of (4.37)
is maximized for
.DS 2
.EQ (4.38)
alpha ~=~ gamma sup -1/2~,
.EN
.DE
and for this choice of $alpha$,
(4.37) reduces to (after neglecting
the $1+ o(1)$ factor)
.DS 2
.EQ (4.39)
2 gamma ~ log sub e ~ 2 ~>=~
beta ~ log sub e ~ 2 ~+~ 2 over 3 ~
beta sup -1 gamma sup 1/2~.
.EN
.DE
To minimize the asymptotic running
time of the algorithm, we have to
choose $beta$ and $gamma$ so that
(4.39) is satisfied and 
$max ~ ( 2 gamma ,~ 2 beta )$ is
minimized.
A short calculation shows that
the optimal choice is
obtained when $gamma~=~ beta $
and equality holds in (4.37), which
yields
.DS 3
.EQ (4.40)
beta~=~
2 sup 2/3 3 sup -2/3 ~~
( log sub e ~ 2 ) sup -2/3 ~=~ 0.9743... ~.
.EN
.DE
The running time for this choice is
.DS 2
.EQ
K sup {2 beta ~ log sub e ~2}
~=~ K sup 1.3507... ^,
.EN
.DE
and the space required is
$K sup {beta ~ log sub e ~2} ~=~ K sup 0.6753...$.
.P
The analysis above assumed that $alpha$, $beta$,
and $gamma$ could all be treated as continuous
variables.
This is essentially true in the case of
$beta$ and $gamma$, but not in the case
of $alpha$, since (4.34a) has to hold
with $k$ a positive integer.
Since the analysis is straightforward
but tedious, we do not discuss the general
situation in detail but only mention that
the running time of the Coppersmith
algorithm
and the space required are of the form
$K sup u$, where $u$ is a
function
of $log sub 2 ~ ( n sup 1/3 ~ ( log sub e ~ n ) sup 2/3 )$
which is periodic with period 1.
The minimal value of $u$ is
$2 beta~log sub e ~2$, with $beta$
given by (4.40), while the
maximal value of $u$ is
$3 sup 2/3 beta ~ log sub e ~ 2~=~ (2.08008...) ~beta ~log sub e ~2$.
Thus we are faced with the not uncommon
situation in which the running time
of
the algorithm does not satisfy a simple
asymptotic relation but exhibits periodic
oscillations.
.P
We next discuss the second stage of the
Coppersmith algorithm, which computes
logarithms of arbitrary elements.
It is somewhat more involved than the
second stage of the basic version of the
algorithm.
If $h$ is a polynomial whose logarithm
is to be determined, then Coppersmith's
second stage consists of a
sequence of steps which replace
$h$ by a sequence of polynomials
of decreasing degrees.
The first step is similar to the
second stage of the basic algorithm
and consists of selecting a random
integer $s$, forming $h sup *$ as
in (4.1), and checking whether $h sup *$
has all its irreducible factors of degrees
$<=~ n sup 2/3 ~ ( log sub e ~ n) sup 1/3$,
say.
(In practice, one would again replace
$h sup *$ by $w sub 1 / w sub 2$,
where the degrees of the $w sub i$
are $<wig~ h/2$, and the bound on the
degrees of the irreducible factors might
be somewhat different, but that is not
very important.)
The probability of success is approximately
$p( n,~ n sup 2/3 ( log sub e ~n) sup 1/3 )$,
so we expect to succeed after
.DS 2
.EQ (4.41)
p ( n,~ n sup 2/3 ( log sub e~n) sup 1/3 ) sup -1 ~=~
K sup {log sub e ~ 3} ~=~
K sup {1.098 "..."}
.EN
.DE
trials.
When we do succeed with some value of $s$,
we obtain
.DS 2
.EQ
h~==~g sup -s ~ prod from i ~ u sub i~~~
( roman mod~ f ( x) )~,
.EN
.DE
where the $u sub i$ are of degrees
$<=~ n sup 2/3 ~ ( log ~ n ) sup 1/3$,
and there are $<~n$ of them (since their
product is a polynomial of degree $<~n$).
This then yields
.DS 2
.EQ (4.42)
log sub g~ h ~==~ - s ~+~
sum from i~ log sub g ~ u sub i ~~~
( roman mod~ 2 sup n -1 )~,
.EN
.DE
and so if we find the $log sub g ~ u sub i$,
we obtain $log sub g ~h$.
.P
Suppose next that $u$ is a polynomial of
degree $<=~ B~<=~ n sup 2/3 ~ ( log ~n) sup 1/3 $
(say one of the $u sub i$ above,
in which case $B~=~n sup 2/3 ~ ( log ~n) sup 1/3 )$.
We again reduce the problem of computing
$log sub g~u$ to that of computing
logarithms of several polynomials of lower degrees.
We select
$2 sup k$ to be a power of 2 close to
$(n/B) sup 1/2$ (precise choice to be specified later), and let
.DS 2
.EQ (4.43)
d~=~ \(lf n2 sup -k \(rf ~+~ 1~.
.EN
.DE
Consider polynomials
.DS 2
.EQ (4.44)
w sub 1 (x)~=~ v sub 1 (x) x sup d ~+~
v sub 2 (x) ~,
.EN
.DE
where
$roman deg ~ v sub 1 (x)$,
$roman deg ~ v sub 2 (x)~<=~ b$
($b$ to be specified later),
$(v sub 1 (x ) ,~ v sub 2 (x) )~=~1$,
and $u(x) | w sub 1 (x)$.
If
.DS 2
.EQ (4.45)
w sub 2 (x) ~==~
w sub 1 (x) sup {2 sup k} ~~~( roman mod ~ f(x) ) ~,~~~
roman deg~ w sub 2 (x) ~<~n~,
.EN
.DE
then (for $b$ small)
.DS 2
.EQ
w sub 2 (x) ~=~ v sub 1 ( x sup {2 sup k} ) x sup {d2 sup k -n}
f sub 1 (x) ~+~ v sub 2 (x sup {2 sup k} )~,
.EN
.DE
and thus $w sub 1 (x)$ and 
$w sub 2 (x)$ both have low
degrees.
If $w sub 1 (x) / u (x)$
and $w sub 2 (x)$ both factor into
irreducible polynomials of low
degree, say
.DS 3
.EQ
w sub 1 (x )~mark =~
u (x) ~ prod from i~ s sub i (x)~,
.EN
.sp
.EQ
w sub 2 (x )~lineup =~
prod from j ~ t sub j (x)~,
.EN
.DE
then we obtain
.DS 3
.EQ
sum from j~log sub g ~ t sub j (x ) ~mark ==~
log sub g ~ w sub 2 (x) ~==~
2 sup k ~ log sub g ~ w sub 1 (k)
.EN
.sp
.EQ
lineup ==~
2 sup k ~ ( log sub g ~ u (x) ~+~ sum from i ~
log sub g ~ s sub i (x) ) ~~~ ( roman mod~
2 sup n -1 )~.
.EN
.DE
This reduces the computation of $log sub g ~u$
to the computation of the $log sub g ~ t sub j$
and the $log sub g ~u sub i$.
We next analyze how much of a reduction
this is.
The probability that $w sub 1 (x) / u (x)$
and $w sub 2 (x)$ both factor into
irreducible polynomials of degrees $<=~ M$
is approximately
.DS 2
.EQ
p ( d + b - roman deg~ u(x) ,~ M) ~
p ( b2 sup k + 2 sup k + roman deg~ f sub 1 (x) ,~
M)~,
.EN
.DE
and the number of pairs of polynomials
$v sub 1 (x ),~ v sub 2 (x )$ of
degrees $<=~b$ with
$( v sub 1 (x ),~ v sub 2 (x) )~=~1$ and
$u (x ) ~|~ w sub 1 (x)$ is approximately
.DS 2
.EQ
2 sup {2b - roman deg ~ u (x)} ~.
.EN
.DE
(Divisibility by $u(x)$ is determined by
a set of $roman deg~ u(x)$ linear
equations for the coefficients of
$v sub 1 (x)$ and $v sub 2 (x)$.)
Hence to find $v sub 1 (x)$ and $v sub 2 (x)$
such that $w sub 1 (x)$ and $w sub 2 (x)$
factor in the desired fashion we select
$b$ to be approximately
.DS 2
.EQ (4.46)
( n sup 1/3 ~ ( log sub e ~ n ) sup 2/3 
( log sub e ~2 ) sup -1~+~
roman deg ~ u (x) ) /2 ~,
.EN
.DE
and select $2 sup k$ to be the power
of 2 nearest to $(n/b) sup 1/2$.
We then expect to obtain the desired
factorization in time
.DS 2
.EQ
K~=~exp ( ( 1+o(1)) n sup 1/3
( log sub e ~n) sup 2/3 )~,
.EN
.DE
with $M$ being the largest integer for
which
.DS 2
.EQ (4.47)
Kp ( d+b- roman deg ~u(x),~M)
p ( b 2 sup k + 2 sup k + roman deg~
f sub 1 (x),~ M) ~>=~1~.
.EN
.DE
.P
If $B~wig~n sup 2/3 ( log sub e ~n) sup 1/3$
(as occurs in the first step of the second
stage of the Coppersmith algorithm), we
find that we can take $M~wig~cn sup 1/2 ( log sub e ~n ) sup 3/2$,
and if
$B~wig~cn sup 1/2 ( log sub e ~n) sup 3/2$,
then we can take $M~wig~c prime n sup 5/12 ( log sub e ~n) sup 25/12$.
More generally, it is also easy to show
that if $B~>=~ n sup 1/3 ( log sub e ~n) sup 2/3$,
say, then we can take
$M~<=~B/1.1$, so that each iteration
decreases the degrees of the polynomials
whose logarithms we need to compute
by a factor $>=~1.1$,
while raising the number of these polynomials
by a factor $<=~n$.
When $B~<=~ (1.1) sup -1 n sup 1/3 ( log sub e ~n) sup 2/3$,
the polynomial $u(x)$ is already in our data
base, and we only need to read off its
logarithm.
Thus we expect to perform
.DS 2
.EQ
<=~exp ( c prime prime ( log~n) sup 2 )~=~K sup o(1)
.EN
.DE
iterations of this process,
each iteration taking $K$ steps.
.P
We have shown that the second stage
of the Coppersmith algorithm can compute
individual logarithms in time
$K sup {1.098 "..."}$.
In fact, with slightly more care the
exponent of $K$ can be lowered substantially.
We do not do it here,
since the main point
we wish to make is that
as in the basic algorithm,
the second stage of the
Coppersmith variant requires
very little time and negligible
space, compared to the first stage.
.P
This section was devoted almost
exclusively to the asymptotic
analysis of the index-calculus
algorithms on a random access
machine.
In Section 6 we will consider
the question of estimating the
running time of this algorithm
for some concrete values of
$n$, including the possible
effects of the use of
parallel processors.
In the next section we will discuss
several variations on the
algorithm as it has been
presented so far.
.H 1 "Further modifications of the index-calculus algorithm"
Section 4 was concerned largely
with the asymptotic behavior of
the index-calculus algorithm in
fields $GF (2 sup n )$.
This section will discuss several technical issues
related to both the basic algorithm and the Coppersmith
version.
The most important of them is that of efficient solutions
to systems of linear equations, discussed in Section 5.7.
The fact that the equations that occur in index-calculus
algorithms can be solved fast is a recent discovery which
affects the estimates of the running time both asymptotically
and in practice.
.P
This section also presents a variety
of modifications of both the basic
algorithm and of the Coppersmith version,
which do not affect the asymptotics of
the running times very much, but which are
very important in practice.
The most significant of these variations is that
of Section 5.6.
That variation speeds
up the first phase of the Coppersmith algorithm
by two or three orders of magnitude in fields
that might be of practical interest.
The variations presented here are not analyzed
in exhaustive detail because their
exact contributions depend on the
hardware and software in which
the algorithm is implemented.
The purpose here is to obtain
rough estimates of the performance
of the algorithm with the best
currently conceivable techniques.
These estimates will be used in
the next section to evaluate how
large $n$ ought to be to offer
a given level of security.
.H 2 "Systematic equations"
The first stage of the index-calculus
algorithm involves the collection of
slightly over $| S |$ linear
equations for the logarithms of the
polynomials $v~member~S$ and then
the solution of these equations.
The reason the Coppersmith version
is so much faster than the Blake
et al. version is that by dealing
with pairs of polynomials of degree
around $n sup 2/3$ as opposed of
degree about $n/2$, it increases
the probability of finding an
additional equation for the
$log sub g ~v$,
$v~member~S$.
In fact, for the fields $GF (2 sup n )$,
Blake et al. had some methods for obtaining
large numbers of equations at very low
cost per equation.
They called the equations obtained this
way ``systematic.''
They were able to obtain upwards of one
half of the required number of equations
that way, but never all.
Their methods in fact inspired Coppersmith
to invent his version of the algorithm.
We will now explain the Blake et al. methods
and explore their significance.
These methods work best when the
polynomial $f(x)$ which
defines the field has the special
property that it divides some
polynomial of the form
.DS 2
.EQ (5.1)
x sup {2 sup k} ~+~f sub 1 (x)~,
.EN
.DE
where the degree of $f sub 1 (x)$
is very small, and where the
primitive element $g~=~g(x)~=~x$.
In general, it appears likely that
the degree of $f sub 1 (x)$ will
be relatively high, which will
make these new approaches of Blake et al.
of little significance.
In some cases, however, these methods
produce startling improvements.
This happens, for example, in the
case of $n~=~127$, when we take the
defining polynomial to be
$f(x)~=~x sup 127 + x + 1$, since here
.DS 2
.EQ
xf(x)~=~x sup {2 sup 7} + x sup 2 + x~,
.EN
.DE
and
$f sub 1 (x)$ has degree 2.
.P
The first of the observations made by
Blake and his collaborators is that
if $f sub 1 (x)$ is of low degree,
the polynomials $x sup {2 sup r}$,
$1~<=~r~<=~n-1$, will often have low
degree when reduced modulo $f(x)$.
When this degree is low enough to
make that polynomial a product of
polynomials from $S$, we obtain a
linear equation of the desired kind,
since $log sub x x sup {2 sup r} ~=~2 sup r$.
As an example, for $n~=~127$ and
$f(x)~=~x sup 127 + x +1$, we find that
for $7~<=~i~<=~126$,
.DS 2
.EQ
x sup {2 sup i}~=~
( x sup {2 sup 7} ) sup {2 sup i-7} ~=~
( x sup 2 + x ) sup {2 sup i-7} ~=~
x sup {2 sup i-6} +
x sup {2 sup i-7} ~,
.EN
.DE
and repeated application of this
result shows that each
$x sup {2 sup r}$, $0~<=~r~<=~126$,
can be expressed in the form
.DS 2
.EQ
sum from i=0 to 6~ epsilon sub i x sup {2 sup i} ~,~~~
epsilon sub i~=~0 ,~1 ~,
.EN
.DE
and so the logarithms of all such
elements can be quickly computed,
and are of the form $2 sup r$
for some $r$.
Furthermore,
since
.DS 2
.EQ
1+ x sup {2 sup r} ~=~
(1+x) sup {2 sup r} ~=~x sup {127.2 sup r}~,
.EN
.DE
one can also obtain the logarithms of all
elements of the form
.DS 2
.EQ
epsilon sub -1 ~+~
sum from i=0 to 6~
epsilon sub i x sup {2 sup i} ~,~~~
epsilon sub i~=~0,~1 ~.
.EN
.DE
In particular, these will include the
logarithms of 31 nonzero polynomials
of degrees $<=~16$.
In general, for other values of $n$,
$f sub 1 (x)$ will not have such a
favorable form, and we can expect fewer
usable equations.
.P
Another observation of Blake et al.,
which is even more fruitful, is
based on the fact that if
$u(x)$ is any irreducible
polynomial over $GF(2)$ of degree
$d$, and $v(x)$ is any polynomial
over $GF (2)$, then the degrees
of all irreducible factors of
$u(v(x))$ are divisible by $d$.
To prove this, note that if $w(x)$
is an irreducible factor of $u(v(x))$,
and $alpha$ is a root of $w(x)~=~0$,
then $v( alpha )$ is a zero of $u(x)$,
and thus is of degree $d$ over
$GF(2)$.
Since $v(x)$ has its coefficients in
$GF(2)$, this means that $alpha$
must generate an extension field
of $GF (2 sup d )$, which means
that its degree must be divisible
by $d$, as we wished to show.
.P
To apply the above fact, Blake et al.
take an irreducible $u(x)$ of low
degree, $u(x)~member~S$, and note that
by (5.1),
.DS 2
.EQ
u(x  ) sup {2 sup k }~=~
u( x sup {2 sup k } ) ~=~
u(f sub 1 (x))~.
.EN
.DE
If $u(f sub 1 (x) )$ factors into
polynomials from $S$, one obtains
another equation for the logarithms
of the $v~member~S$.
The result proved in the preceding
paragraph shows that all the factors
of $u(f sub 1 (x))$ will have
degrees divisible by $roman deg~u(x)$,
and not exceeding $( roman deg~ u(x))~ ( roman deg~ f sub 1 (x))$.
Blake and his collaborators
noted that in many cases all
the irreducible factors have
degrees actually equal to
$roman deg~u(x)$.
We will now discuss the
likelihood of this happening.
.P
Suppose that
.DS 2
.EQ (5.2)
f(x) ~~|~~ x sup {2 sup k} + f sub 1 (x)~~.
.EN
.DE
We can assume without loss of generality
that not all powers of $x$
appearing in $f sub 1 (x)$
are even, since if they were, say
$f sub 1 (x)~=~f sub 2 ( x sup 2 ) ~=~f sub 2 (x) sup 2$,
we would have
.DS 2
.EQ
f(x) ~~|~~ x sup {2 sup k} +
f sub 2 (x) sup 2 ~=~( x sup {2 sup k-1} +
f sub 2 (x) ) sup 2 ~,
.EN
.DE
and since $f(x)$ is irreducible, we
would obtain
.DS 2
.EQ
f(x) ~~|~~ x sup {2 sup k-1} + f sub 2 (x) ~~,
.EN
.DE
and we could replace $f sub 1 (x)$ by
$f sub 2 (x)$ in (5.2).
Therefore we will assume $f sub 1 (x)$
does have terms of odd degree, and so
$f sub 1 sup prime (x)~!=~0$.
.P
The polynomial
.DS 2
.EQ (5.3)
F sub d (x) ~=~x sup {2 sup d} + x
.EN
.DE
is the product of all the irreducible
polynomials of all degrees dividing
$d$.
When we substitute $f sub 1 (x)$ for $x$ in
$F sub d (x)$, we obtain
.DS 2
.EQ (5.4)
F sub d ( f sub 1 (x))~=~
f sub 1 (x) sup {2 sup d} + f sub 1 (x)~=~
f sub 1 ( x sup {2 sup d} ) + f sub 1 (x)~.
.EN
.DE
But
.DS 2
.EQ
f sub 1 ( x sup {2 sup d} ) + f sub 1 (x)~==~
f sub 1 (x) + f sub 1 (x) ~=~0~~~
( roman mod~ F sub d ( x ))~,
.EN
.DE
and so each irreducible polynomial whose
degree divides $d$ has to divide some
$u( f sub 1 (x))$ for another irreducible
$u(x)$ of degree dividing $d$.
Since
.DS 2
.EQ
d over dx~
F sub d ( f sub 1 (x) )~=~f sub 1 sup prime (x)
.EN
.DE
by (5.4), only a small number of irreducibles
can divide $F sub d (f sub 1 (x))$ to second
or higher powers.
Hence we conclude that at most only about
one in $roman deg~ f sub 1 (x)$ of the
irreducible polynomials $u(x)$ of degree
$d$ can have the property that
$u( f sub 1 (x))$ factors into irreducible
polynomials of degree $d$.
Thus if we have only one pair
$(k,~ f sub 1 (x))$ for which (5.2)
holds, then we can expect at most about
$| S | / ( roman deg~ f sub 1 ( x ))$
systematic equations from this method.
We also obtain useful equations from all
$u(x)$ for which $roman deg ~ u(f sub 1 (x))~<=~m$,
but there are relatively few such polynomials
$u(x)$.
If $roman deg~ f sub 1 (x)~=~2$
(as it is for $n~=~127$, $f(x)~=~x sup 127 + x + 1 $),
it is easy to see that almost
exactly one half of the irreducible
polynomials
$u(x)$ of a given degree $d$ will have
the property that $u( f sub 1 (x))$
factors into irreducible polynomials
of degree $d$.
If $roman deg~ f sub 1 (x)~>~2$,
the situation is more complicated,
in that the $u(f sub 1 (x))$ can
factor into products of irreducible
polynomials of several degrees, and
so the number of useful equations
obtained this way is typically
considerably smaller than
$| S | / ( roman deg~ f sub 1 (x))$.
.P
One factor which is hard to predict
is how small can one take the
degree of $f sub 1 (x)$ so that
(5.2) holds for some $k$ and some
primitive polynomial $f(x)$ of
degree $n$.
The situation for $n~=~127$, where
we can take $f sub 1 (x) ~=~x sup 2 + x $,
is extremely favorable.
For some $n$, it is possible to
take $roman deg~ f sub 1 (x)~=~1$.
Condition (5.2) with $f sub 1 (x)~=~x$
is not useful, since it holds precisely
for the irreducible polynomials of
degrees dividing $k$, and the resulting
discrete logarithm equations simply
say that
.DS 2
.EQ
2 sup k ~ log sub x v~==~
log sub x v ~ ( roman mod~ 2 sup d -1 )
.EN
.DE
for $d | k$, $d~=~roman deg~ v(x)$,
which is trivial.
Condition (5.2) with $f sub 1 (x) ~=~x+1$
is somewhat more interesting.
If it holds, then
.DS 2
.EQ
f(x) ~~|~~ x sup {2 sup 2k} + x~,
.EN
.DE
and thus $roman deg ~ f(x) ~~|~~ 2k$.
On the other hand, because of (5.2),
$roman deg~ f(x)~"\o'|\(sl'"~k$.
Thus this condition can hold only
for even $n$, which, as we will
argue later, ought to be avoided
in cryptographic applications.
For these even $n$, however, it
gives relations of the form
.DS 2
.EQ
2 sup n/2 log sub x v~==~ log sub x v sup *
~~~( roman mod~ 2 sup n -1 )~,
.EN
.DE
for all irreducible $v(x)$, where
$v sup * ( x )~=~ v (x+1 )$,
and then gives about $| S | /2$
useful equations.
.P
In many cases it is impossible to find
$f(x)$ of a given degree such that
(5.2) holds for some $f sub 1 (x)$
of low degree.
When such $f(x)$ can be found, it
sometimes happens that (5.2) holds
for several pairs $( k,~ f sub 1 (x))$.
For example, when $n~=~127$,
$f(x) ~=~x sup 127 + x +1$, condition
(5.2) holds for $k~=~7$,
$f sub 1 (x) ~=~x sup 2 +x$ and also
for $k~=~14$, $f sub 1 (x) ~=~x sup 4 + x$.
.P
The significance of these systematic
equations is not completely clear.
Our arguments indicate that unless
(5.2) is satisfied with $f sub 1 (x)$
of low degree, few systematic equations
will be obtained.
No method is currently known for finding
primitive $f(x)$ of a given degree $n$
for which (5.2) is satisfied with some
$f sub 1 (x)$ of low degree.
It is not even known whether there
exist such $f(x)$ for a given $n$.
Even in the very favorable situation
that arises for $n~=~127$,
$f(x)~=~x sup 127 + x + 1$,
Blake et al. [8] found only 142
linearly independent systematic
equations involving the 226 logarithms
of the irreducible polynomials of
degrees $<=~10$.
(They reported a very large number of
linear dependencies among the systematic
equations they obtained.)
Thus it seems that while systematic
equations are a very important idea
that has already led to the
Coppersmith breakthrough and might
lead to further developments,
at this time they cannot be relied upon
to produce much more than $| S | /2$
equations, and in practice probably
many fewer can be expected.
.H 2 "Change of primitive element and field representation"
The Coppersmith algorithm requires that
the polynomial $f(x)$ that generates
the field $GF ( 2 sup n )$ be of the
form (4.18) with $f sub 1 (x)$ of
low degree.
Section 4.1 showed that if the
$f(x)$
satisfies (5.2) with $f sub 1 (x)$
if low degree, and $x$ is a
primitive element of the field,
one can obtain many systematic
equations.
On the other hand, it is often
desirable that $f(x)$ satisfy
other conditions.
For example, if $f(x)$ is an irreducible
trinomial,
.DS 2
.EQ (5.5)
f(x)~=~x sup n + x sup k +1~,
.EN
.DE
where we may take $k~<=~n/2$, since
$x sup n + x sup n-k +1$ is irreducible
if and only if $f(x)$ is, then
reduction of polynomials modulo $f(x)$
is very easy to implement; if
.DS 2
.EQ
h(x)~=~sum from i=0 to 2n-2~a sub i x sup i
.EN
.DE
(as might occur if $h(x)$ is the product
of two polynomials reduced modulo $f(x)$),
then
.DS 2
.EQ (5.6)
h(x)~==~
sum from i=0 to n-1~
a sub i x sup i ~+~
sum from i=0 to n-2~
a sub i+n x sup i~+~
sum from i=k to k+n-2~
a sub i+n-k x sup i ~~~( roman mod~ f(x))~,
.EN
.DE
a reduction that can be accomplished
using two shifts and two exclusive
or's of the coefficient strings, and
another iteration of this procedure
applied to the polynomial on the
right side of (4.6) yields the fully
reduced form of $h(x)$.
It is often also desirable that $f(x)$
be primitive, since then $x$ can be
used as a primitive element of the
field.
(Extensive tables of primitive
trinomials are available, see [28,71,72].)
In some cases, of which $n~=~127$
and $f(x)~=~x sup 127 + x + 1$ is the
example par excellence, it is possible
to satisfy all these desirable
conditions.
In general, though, some kind of compromise
might be necessary, and the choice to be
made might depend both on $n$ (and thus
on what kinds of polynomials exist) and
on the hardware and software that are being
used.
Our purpose here is to show that the
security of a cryptosystem is essentially
independent of the choices that are
made; the cryptosystem designer and the
cryptanalyst can choose whichever $f(x)$
and $g(x)$ suit them best.
.P
To show that changing only the primitive
element $g(x)$ does not affect the
security of a system, suppose that we
have a way to compute discrete logarithms
to base $g(x)$ efficiently.
If another primitive element $g sub 1 (x)$
and a nonzero polynomial $h(x)$ are
given, and it is desired to compute the
logarithm of $h(x)$ to base $g sub 1 (x)$,
we compute the logarithms of $g sub 1 (x)$
and $h(x)$ to base $g(x)$, say
.DS 3
.EQ
g sub 1 (x)~mark ==~
g(x) sup a ~~~( roman mod~ f(x))~,
.EN
.sp
.EQ
h(x)~lineup ==~
g(x ) sup b ~~~( roman mod~ f(x) )~,
.EN
.DE
and obtain immediately
.DS 2
.EQ
h(x)~==~g sub 1 (x ) sup {a sup * b}
~~~( roman mod~ f(x))~,
.EN
.DE
where $a sup *$ is the integer with
$1~<=~a sup * ~<=~ 2 sup n -1$ for which
.DS 2
.EQ
aa sup *~==~1~~~( roman mod~ 2 sup n -1)~.
.EN
.DE
(Since $g(x)$ and $g sub 1 (x)$ are
primitive, $( a sub 1 2 sup n -1) ~=~1$,
and so $a sup *$ exists.)
.P
Changing the representation of the field,
so that it is given as polynomials modulo
$f sub 1 (x)$, as opposed to modulo $f(x)$,
also does not affect the difficulty of
computing discrete logarithms,
as was first observed by Zierler\ [70].
The two fields are isomorphic, with the
isomorphism being given by
.DS 2
.EQ
x~( roman mod~ f sub 1 (x) )~->~
h(x)~~~( roman mod~ f(x))~,
.EN
.DE
where
.DS 2
.EQ
f sub 1 ( h(x))~==~0~~~
( roman mod ~ f(x))~.
.EN
.DE
Thus to construct the isomorphism we have to find a root
$h(x)$ of $f sub 1 (x)$ in
the field of polynomials modulo $f(x)$.
Such a root can be found in time
polynomial in $n$ [7,16,36,55,70],
which establishes the isomorphism
and enables one to transfer logarithm
computations from one representation
to another.
.H 2 "Faster generation and processing of test polynomials"
As we described the basic index-calculus
algorithm, the polynomials $h sup *$
are generated (in the first stage of
the algorithm, say) by selecting a
random integer $s$ and reducing $g sup s$
modulo $f(x)$.
Typically this involves on the order of
$3n/2$ polynomial multiplications and
reductions modulo $f(x)$.
This work can be substantially reduced
by choosing the $h sup *$ in succession,
say
$h sub 1 sup *~=~1 ,~ h sub 2 sup * ,~
h sub 3 sup * ,"..."$, with
.DS 2
.EQ
h sub k+1 sup *~==~ h sub k sup * v sub s~~~
( roman mod~ f(x))~,
.EN
.DE
where $v sub s$ is chosen at random from $S$.
This requires only one polynomial
multiplication (in which one factor,
namely $v sub s$, is of low degree)
and one reduction.
Since each $h sub k sup *$ is of the form
.DS 2
.EQ
h sub k sup *~==~ prod from {v member S}~
v sup {a sub v} ~~~( roman mod~ f(x))~,
.EN
.DE
any time we find that both $w sub 1$ and $w sub 2$
have all their irreducible factors in $S$, we
obtain another equation
for the $log sub g v , ~~v ~member~S$.
Heuristic arguments and some empirical evidence [58]
indicate that the sequence $h sub k sup *$
ought to behave like a random walk in
$GF( 2 sup n ) \e "{" 0 "}"$, which means
that the modified algorithm ought to produce
linear equations about as efficiently as the old one.
.P
Once $h sup *$ is computed,
the $(w sub 1 ,~ w sub 2 )$
pair that satisfies (4.7) is
produced by the extended
Euclidean algorithm applied
to the polynomials $h sup *$
and $f$, which are each of
degree about $n$.
It might be advantageous
to decrease the cost of
this relatively slow operation
by generating several pairs
$( w sub 1 ,~ w sub 2 )$ that
satisfy (4.7).
This can be done by choosing
$w sub 1~=~gamma sub j$ and
$w sub 2~=~alpha sub j$ for
several values of $j$ such that
(4.11) holds and the degrees
of the $w sub i$ are not too
far from $n/2$.
As is shown in Appendix A,
.DS 2
.EQ
p( r+s ,~ m) p ( r-s ,~ m ) ~approx~
p( r,~ m ) sup 2
.EN
.DE
for $s$ small compared to $r$
(for example,
$p( 105,~18) p( 95,~18)~=~1.07 times 10 sup -8$,
while
$p(100,~ 18 ) sup 2 ~=~1.09 times 10 sup -8$)
so that if the neighboring pairs
$( gamma sub j , ~ alpha sub j )$
that satisfy (4.11) are independent
with regard to factorization into small
degree irreducible polynomials, as seems
reasonable, we can cheaply obtain
additional pairs $(w sub 1 , ~ w sub 2 )$
satisfying (4.7) which will be just as
good in producing additional equations.
.P
The two modifications suggested above can
also be applied to the second stage of
the basic index-calculus algorithm, where they
will lead to a similar improvements in running
time.
They can also be used in the first step of
the second stage of the Coppersmith algorithm.
.P
Blake et al. [8] used the Berlekamp
algorithm [7] to factor the polynomials
$w sub i$.
However, what is really needed initially
is only to check whether all the irreducible
factors of the $w sub i$ are of degrees
$<=~m$.
The complete factorization of the $w sub i$
is needed only when the $w sub i$ are
both composed of low degree factors,
and this happens so infrequently that
the time that is needed in those cases
to factor the $w sub i$ is an
insignificant fraction of the total
running time.
Now to rapidly check whether a
polynomial $w(x)$ has all its
irreducible factors of degrees
$<=~m$, we can proceed as follows.
Since the greatest common divisor,
$( w prime (x) ,~ w (x) )$, of
$w(x)$ and its derivative
equals
.DS 2
.EQ (5.7)
( w sup prime (x),~ w (x))~=~
prod from i~
y sub i (x) sup {2 [ a sub i /2 ]}~,
.EN
.DE
where
.DS 2
.EQ
w(x)~=~
prod from i~
y sub i (x) sup {a sub i} ~,
.EN
.DE
and the $y sub i (x)$ are distinct
irreducible polynomials, we can
compute
.DS 2
.EQ
w sup (0) (x)~=~ prod from i~
y sub i (x)
.EN
.DE
in a few greatest common divisor
and square root operations.
Then, for $i~=~1, 2, "..." ,~ m$
we
compute
.DS 2
.EQ (5.8)
w sup (i) (x)~=~{w sup (i-1) (x)} over
{( w sup (i-1) (x) ,~ x sup {2 sup i} +x )}
~.
.EN
.DE
Since $x sup {2 sup k} ~+~x$ is the product
of all the irreducible polynomials of
degrees dividing $k$,
$w sup (m) (x)~=~1$ if and only if all
the irreducible factors of $w(x)$ are
of degrees $<=~m$.
.P
The above procedure ought to be quite fast,
since the greatest common divisor
of two polynomials of degrees $<=~ n$
can be computed using at most $n$
shifts and exclusive or's of their
coefficient sequences
and since the degrees of the $w sup (i)$
are likely to decrease rapidly.
The above procedure can be simplified
some more by noting that it suffices
to define
$w sup {( i sub 0 )} (x)~=~w sup (0) (x)$
for $i sub 0~=~[(m-1)/2]$ and
apply (5.8) for $i~=~i sub 0 +1 , "..." ,~ m$,
since any irreducible polynomial
of degree $d$, $d~<=~m$, divides
at least one of the
$x sup {2 sup i} +x$,
$i sub 0 +1~<=~ i~<=~m$.
Furthermore, the $x sup {2 sup i} +x$
do not have to be computed at each stage
separately, but instead, if we save
.DS 2
.EQ
u sub i ( x)~==~ x sup {2 sup i} + x~~~
( roman mod~ w sup (i-1) (x))~,
.EN
.DE
with $u sub i (x)$ reduced modulo
$w sup (i-1) (x)$, then
.DS 2
.EQ
u sub i (x) ~==~ x sup {2 sup i} +x ~~~
( roman mod~ w sup (i) (x))~,
.EN
.DE
and so
.DS 2
.EQ
u sub i+1 (x)~==~
u sub i ( x sup 2 ) +x sup 2 + x ~~~
( roman mod~ w sup i (x) )~,
.EN
.DE
which is a much simpler operation.
.P
Another fast way to test whether a polynomial
$w(x)$ has all its irreducible factors of
degrees $<=~ m$ was suggested by
Coppersmith [19].
It consists of computing
.DS 2
.EQ
w sup prime ( x) ~ prod from { i ~=~ \(lc m/2 \(rc} to m~
( x sup { 2 sup i} + x ) ~~~( roman mod~ w(x) )~,
.EN
.DE
and checking whether the resulting
polynomial is zero or not.
This method avoids the need for
many greatest common division
computations, and so may be
preferable in some implementations.
It is not completely foolproof, since polynomials in
which all irreducible factors of degrees $> m$ appear
to even powers will pass the test.
However, such false signals will occur very infrequently,
and will not cause any confusion, since polynomials
$w(x)$ that pass the Coppersmith test have to be
factored in any case.
.H 2 "Large irreducible factors"
This section discusses a variation
on both the basic index-calculus algorithm
and the Coppersmith variation
that was inspired by the "large prime"
variation on the continued fraction
integer factoring method (cf. [53]).
In practice, as will be discussed
in greater length later, the $w sub i$
would probably be factored by removing from
them all irreducible factors of
degree $<=~m$,
and
discarding that pair $(w sub 1 ,~ w sub 2 )$
if either one of the quotients
is not 1.
If one of the quotients, call it
$u(x)$, is not 1, but has degree
$<=~2m$, then it has to be
irreducible.
The new variation would use such
pairs, provided the degree of
$u(x)$ is not too high
($<=~ m+6$, say).
The pair $(w sub 1 ,~ w sub 2 )$
that produced $u(x)$ would be
stored, indexed by $u(x)$.
Then, prior to the linear
equation solving phase, a preprocessing
phase would take place, in which
for each irreducible $u(x)$,
$roman deg ~ u(x)~>~m$,
the pairs $( w sub 1 ,~ w sub 2 )$
that are associated to it would be
used to obtain additional linear
equations
involving logarithms of the $v~member~S$.
For example, in the basic algorithm, if
there are $k$ pairs associated
to $u(x)$, say
.DS 2
.EQ
h sub i sup *~==~
u sup {a sub i} ~ prod from {v member S} ~
v sup {b sub v (i)} ~~~( roman mod~ f)~,~~~
1~<=~i~<=~ k~,
.EN
.DE
where each $a sub i~=~+- 1$, then we can
obtain $k-1$ equations for the logarithms
of the $v~member~S$ by considering the
polynomials
.DS 2
.EQ
h sub i sup * ( h sub 1 sup * ) sup {- a sub i / a sub 1} ~==~
prod from {v member S} ~
v sup {b sub v (i) - b sub v (1) a sub i /a sub 1 } ~~~
( roman mod~ f )~,~~~
2~<=~ i~<=~ k~.
.EN
.DE
A similar method works with the Coppersmith
variation.
.P
We now consider the question of how
many equations we are likely to
obtain by this method.
Suppose that we generate $N$
different pairs $( w sub 1 ,~ w sub 2 )$,
where each of the $w sub i$ is of degree
approximately $M$ (which would be
$wig~ n/2$ for the basic algorithm
and on the order of $n sup 2/3$
in the Coppersmith variation).
We then expect to obtain about
.DS 2
.EQ
N p ( M,~ m ) sup 2
.EN
.DE
pairs $( w sub 1 ,~ w sub 2 )$, where
each of the $w sub i$ factors into
irreducibles from $S$.
Consider now some $k~>~m$.
The probability that a random
polynomial of degree $wig~ M$
has exactly one irreducible factor
of degree $k$ and all others of
degrees $<=~m$ is about
.DS 2
.EQ
p( M -k,~ m ) I(k) 2 sup -k~,
.EN
.DE
where $I(k)$ is the number of irreducible
polynomials of degree $k$.
Therefore we expect that the probability
that exactly one of $w sub 1$ and $w sub 2$
has one irreducible factor of degree $k$
and all other factors of both $w sub 1$
and $w sub 2$ are of degrees $<=~m$ is about
.DS 2
.EQ
2p ( M - k,~m)
p( M  ,~ m ) I (k) 2 sup -k~.
.EN
.DE
(The probability that both $w sub 1$
and $w sub 2$ have one irreducible
factor of degree $k$ and all others
of degree $<=~m$ is negligible.)
Hence among our $N$ pairs $(w sub 1 ,~ w sub 2 )$
we expect
about
.DS 2
.EQ (5.9)
N sub k~wig~2N ~p ( M ,~ m ) p 
([n/2] - k,~m) I(k) 2 sup -k
.EN
.DE
pairs that would be preserved.
The number of equations that we
expect to obtain from these $N sub k$
pairs is $N sub k - M sub k$,
where $M sub k$ is the number of
irreducible polynomials of degree $k$
that appear in the stored list.
.P
To estimate $M sub k$, we make
the assumption that the irreducible
polynomials $u(x)$ of degree $k$ that
appear in the factorization of the
$w sub i$ behave as if they were
drawn at random from the $I(k)$
such polynomials.
When $N sub k$ balls are
thrown at random into $I(k)$ buckets,
the expected number of buckets that
end up empty is $I(k)$ times the
probability that any single bucket
ends up empty.
Since the probability that a particular
bucket ends up with no balls is
.DS 2
.EQ
{(I(k) - 1) sup {N sub k} } over
{I( k ) sup {N sub k } } ~,
.EN
.DE
the expected number of buckets that we
expect to be occupied is
.DS 2
.EQ
I(k) - I(k) (I(k) - 1 ) sup {N sub k} ~
I(k) sup {- N sub k}~.
.EN
.DE
Therefore we expect to obtain approximately
.DS 2
.EQ (5.10)
N sub k ~+~ I (k) ( ( 1- I(k) sup -1 ) sup {N sub k} -1)
.EN
.DE
additional equations from
polynomials of degree $k$.
Since $N sub k$ will be comparable
to $I(k)$ in magnitude in applications
to the index-calculus algorithm, we
can approximate (5.10) by
.DS 2
.EQ (5.11)
N sub k ~+~ I(k) ~
( exp ( - N sub k /I(k)) - 1 )~.
.EN
.DE
Since (see Appendix A) $I sub k~wig~ 2 sup k k sup -1$
and
.DS 2
.EQ
p(  M  - k,~m) ~wig~
p( M ,~ m ) ~
(Mm sup -1 ~ log sub e ~ M/m ) sup k/m~,
.EN
.DE
(5.9) gives us
.DS 2
.EQ (5.12)
N sub k ~ wig ~
2~Nk sup -1 p ( M,~ m ) sup 2 ~
(Mm sup -1 ~log sub e ~ M/m ) sup k/m~.
.EN
.DE
Since $| S | ~wig~ 2 sup m+1 m sup -1$,
we are interested in $N$ for which
$Np ( M ,~ m ) sup 2$ is on the
order of $2 sup m m sup -1$.
For such $N$, though, (5.11) and (5.12)
show that the number of additional
equations is negligible for $k-m~->~ inf$.
For $k~wig~m$, on the other hand, (5.12) shows that
.DS 2
.EQ
N sub k~wig~
2~M ^ m sup -2 N ~p ( M,~m) sup 2
~ ( log sub e ~ M/m )~,
.EN
.DE
which is
.DS 2
.EQ
wig ~ c prime N p ( M ,~ m ) sup 2
.EN
.DE
for $m~wig ~ c ( M~ log sub e ~M) sup 1/2$,
which is the case
for both the basic algorithm and the Coppersmith variant.
Hence we also have
.DS 2
.EQ
N sub k ~wig~ c {prime prime} I (m)~,
.EN
.DE
and (5.11) then shows that we can expect
.DS 2
.EQ
[ c prime prime -
2 sup k-m ( 1- exp ( -c prime prime 2 sup m-k ) ) ]
I (m)
.EN
.DE
additional equations, where the implied
constants are absolute.
Hence when we sum over $k$, we
find that the total number of
additional equations we can
expect the large irreducible
factor variation to generate
is
proportional to the number
that have to be obtained.
.P
The large irreducible
factor variation
can be quite important for moderate
values of $n$, especially when $m$ is
relatively low, as it might have to
be to make the solution of the system
of linear equations feasible.
For example, for $M~wig~65$,
$m~=~18$, without the large irreducible
factor variation we might expect
to test about $N~approx~1.04 ~times 10 sup 8$
pairs $( w sub 1 ,~w sub 2 )$, whereas
with this variation we expect to need
only about $6.7~times~10 sup 7$.
For $M~wig~65$ and $m~=~12$,
the difference is even more
dramatic, since without the
variation we expect to need
$N~approx~1.3 ~times 10 sup 10$,
while with it we need only
$N~approx~ 3.5~times~10 sup 9$.
For $M~wig~100$ and $m~=~20$
the figures are $N~approx~ 4.9~times~10 sup 11$
and $N~approx~ 2.3~times~10 sup 11$,
respectively, while for $M~wig~100$
and $m~=~18$ they are
$N~approx~2.7~times~10 sup 12$
and $N~approx~1.1~times~10 sup 12$.
Thus for values that are of
cryptographic significance, the
large irreducible variation can
shorten the running time of the
equation generating phase by a
factor of between 2 and 3.
Furthermore, it can speed up
the second stage of the index-calculus
algorithm by an even greater factor,
since in addition to the logarithms
of the $v~member~S$, the cryptanalyst
will possess the logarithms of many
polynomials of degrees $m+1 ,~ m+2 , "..."~$.
.H 2 "Early abort strategy"
Like the large irreducible factor
variation discussed in the
preceding section, the early
abort strategy is also inspired
by a similar technique used in
factoring integers.
Most of the pairs
$( w sub 1 ,~ w sub 2 )$ that
are generated turn out to be
ultimately useless, whether
the large irreducible factor
variation is used or not.
It would obviously be of
great advantage to be able to
select those pairs $( w sub 1 , ~ w sub 2 )$
in which both of the $w sub i$
are likely to factor into
irreducible polynomials from $S$.
The idea behind the early abort
strategy is that a polynomial
is unlikely to have all its
factors in $S$ unless it has
many factors of small degree.
Asymptotically this variation
is unimportant, since factorization
of binary polynomials can be
accomplished in time polynomial
in their degree.
For small values of $n$, though,
this variation can be important,
as will be shown below.
.P
Let $p sub k ( r,~m)$ denote
the probability that a polynomial
of degree $r$ has all its
irreducible factors of degrees
strictly larger than $k$ but
at most $m$.
It is easy to obtain recurrences
for $p sub k ( r,~m)$ similar
to those for $p( r,~m)$ derived
in Appendix A, which enables one
to compute the $p sub k ( r,~m)$
numerically.
(It is also possible to obtain
asymptotic expansions for the
$p sub k ( r,~m)$, but since
we know a priori that the early
abort strategy is unimportant
asymptotically, we will not do it here.)
For a polynomial $w(x)$,
let $w sup * (x)$ denote the
product of all the irreducible
factors of $w(x)$ of degrees $<=~k$
(with their full multiplicity).
Let $Q ( r, ~ R ,~ m , ~ k)$
denote the probability
that a polynomial $w(x)$ of degree
$r$ has all its irreducible factors
of degrees $<=~ m$, that $roman deg~ w sup * ( x )~>=~R$.
Then we easily obtain
.DS 2
.EQ
Q ( r, ~ R , ~ m , ~ k )~=~
sum from {j >= R } ~
p ( j, ~ k ) p sub k ( r-j ,~ m )~.
.EN
.DE
Let $Q sup * ( r,~R,~k)$ denote
the probability that a random
polynomial $w(x)$ of degree $r$
has the property that
$roman deg~ w sup * ( x)~>=~R$.
Then we similarly obtain
.DS 2
.EQ
Q sup * ( r,~R,~k)~=~sum from {j >= R}~
p( j,~k) p sub k ( r-j,~ r-j)~.
.EN
.DE
.P
The early abort strategy with
parameters $( k,~R)$ is to discard
the pair $( w sub 1 ,~ w sub 2 )$
if either $w sub 1 sup * (x)$
or $w sub 2 sup * (x)$ has
degree $<~R$.
Let $A$ represent the time
needed to check whether
both $w sub 1 (x)$ and
$w sub 2 (x)$ have all their
irreducible factors are of
degrees $<=~m$, and let $B$
represent the time involved
in testing whether the degrees
of $w sub 1 sup * (x)$ and
$w sub 2 sup * (x)$ are
both $>=~R$.
Then to obtain one factorization
that gives a linear equation
for the logarithms of the $v~member~S$,
the standard index-calculus
algorithm has to test about
$p( [n/2],~m) sup -2$ pairs
$( w sub 1 ,~ w sub 2 )$ at
a cost of approximately
.DS 2
.EQ (5.13)
A~p( [n/2],~ m) sup -2
.EN
.DE
units of time.
The early abort strategy has
to consider about
$Q( [n/2] , ~ R , ~ m , ~ k ) sup -2$
pairs $( w sub 1 ,~ w sub 2 )$,
but of these only about
$Q sup * ( [n/2],~ R,~ k ) sup 2$
$Q ( [n/2],~R,~ m,~ k ) sup -2$
pairs have to be subjected
to the expensive test of checking
if all their irreducible factors
have degrees $<=~m$.
Hence the work involved in
obtaining an additional linear
equation under the early abort
strategy is about
.DS 2
.EQ (5.14)
"{" B + A~Q sup * ( [n/2],~R,~k) sup 2 "}"~~~
Q ( [ n/2 ] , ~ R , ~ m , ~ k ) sup -2
~.
.EN
.DE
In Table 1 we present
some values of the ratio of the
quantity in (5.14) to that in (5.13):
.DS
.sp 2
.TS
center;
c s s s s
c c c c c
c | c | c | c | c.
\f2Table 1\f1.\ \ Evaluation of the early abort strategy.
.sp 2
$n$	$m$	$k$	$R$	ratio of (5.14) to (5.13)
_
128	16	4	5	$2.47~B/A ~+~ 0.412$
.sp .5
128	16	5	5	$1.73~B/A~+~0.452$
.sp .5
200	20	4	5	$2.67~B/A~+~0.445$
.sp .5
200	20	5	6	$2.32~B/A~+~0.396$
.TE
.sp 2
.DE
We see from this that if $B/A~<wig~1/10$,
then one can reduce the work required
to obtain an additional equation by
30-40%, which might speed up the
algorithm by a factor of approximately 1.5.
.P
The success of the early abort
strategy is crucially dependent
on the ability to quickly find
the divisors $w sub i sup *$
of the $w sub i$ that are composed
only of irreducible factors of
degrees $<=~k$.
If we use the procedure suggested
in Section 5.3, this can be
accomplished quite easily.
Given a polynomial $w(x)$ to be
tested, we compute its square-free
part $w sup (0) (x)$
and go through the first $k$ steps
of the procedure described by (5.8).
If $k~=~4$, this can be simplified
further.
Here we only need to know
.DS 2
.EQ
( w sup 0 ( x ) , ~ x sup 8 +x) ~~~and~~~
( w sup 0 ( x ) , ~ x sup 16 + x ) ~,
.EN
.DE
and these can be computed by reducing
$w sup (0) (x)$ modulo
$x sup 8 ~+~x $ and modulo
$x sup 16~+~x$, respectively, and
looking up the greatest common
divisors in precomputed tables.
We could then decide not to reject
$w(x)$ if the difference of the
degree of $w sup (0) (x)$ and
the sum of the degrees of the two
divisors is small enough.
It might also be advantageous
to avoid computing $w sup (0) (x)$
on the first pass, compute
.DS 2
.EQ
(w (x) ,~ x sup 8 + x ) ~,~~~
( w (x) ,~ x sup 16 + x )~,
.EN
.DE
and accept or reject $w(x)$
depending on how small the
difference between the degree
of $w(x)$ and the sum of the
degrees of those factors is.
.P
One can obtain some further slight
gains by using additional
conditions further along
in the computation of the
$w sup (i) (x)$ defined by (5.8).
It seems safe to say, though,
that the early abort strategy
is unlikely to speed up the
linear equation collection phase
of the index-calculus algorithm
by more than a factor of 2 or so.
.H 2 "Faster generation of equations in Coppersmith's method"
It is possible to significantly
speed up the first stage of
Coppersmith's variant of the
index-calculus algorithm by
applying some of the ideas
that occur in the second stage
of that version.
Asymptotically, the improvements
are not important, but in practice
they are likely to be much more
important than all the other variations
we have discussed so far, and could
speed up the equation-collecting phase of
the algorithm by factors of 10 to 20
for $n~=~127$, by up to 300 for
$n~=~521$,
and by over 1000 for $n~=~1279$.
.P
The idea behind the new variation
is that instead of selecting $u sub 1 (x)$
and $u sub 2 (x)$ to be any pair of
relatively prime polynomials of degrees
$<=~B$ each, we select them to increase the chances of $w sub 1 (x)$
and $w sub 2 (x)$ splitting into low degree
irreducible factors.
To do this, we select a pair $v sub 1 (x)$
and $v sub 2 (x)$ of
polynomials of degrees $<=~ B-1$
(but close to $B$) such that each is composed
of irreducible factors of degrees $<=~m$.
We then select $u sub 1 (x)$ and $u sub 2 (x)$
of degrees $<=~B$ so that
$v sub 1 (x) ~|~ w sub 1 (x)$ and
$v sub 2 (x) ~|~w sub 2 (x)$.
The divisibility condition gives us
$roman deg~ v sub 1 (x) ~+~ roman deg~ v sub 2 (x) ~<=~
2B-2$ homogeneous linear equations for the
$2B$ coefficients of $u sub 1 (x)$ and
$u sub 2 (x)$, and so we obtain at least
3 nonzero solutions.
Moreover, these solutions can be found very
fast, by using gaussian elimination on the
$GF(2)$ matrix of size $<=~ 2B-2$ by $2B$.
.P
When $u sub 1 (x)$ and $u sub 2 (x)$
are selected by the above procedure, the
probability of $w sub 1 (x)$ splitting
into irreducible factors of degrees $<=~m$
ought to be close to $p(h,~m)$, and the
probability of $w sub 2 (x)$ splitting
in this way ought to be close to
.DS 2
.EQ
p(h2 sup k - n + B ( 2 sup k -1 ) ~+~ roman deg~
f sub 1 (x) ,~m)~.
.EN
.DE
Since $B~=~O ~ (n sup 1/3 ~ ( log sub e ~ n) sup 2/3 )$,
the form of the asymptotic estimate for the
probability of both $w sub 1 (x)$ and $w sub 2 (x)$
splitting is not affected by this improvement.
In practice, however, the improvements can be
vital.
.P
Some care has to be used in the application of
the idea proposed above.
The first stage of the index-calculus
algorithm requires the generation of
$| S | ~wig~ m sup -1 2 sup m+1$ linearly
independent equations.
The equations generated by the basic version
of the algorithm and by the Coppersmith
variation are expected to be largely independent
of the preceding ones (as long as there are $<~ | S |$ of them)
on heuristic grounds, and this is
confirmed by computational experience.
That is not the case, however, with
the variation proposed above, because
in general many pairs
$( v sub 1 (x),~ v sub 2 (x) )$ will
give rise to the same pair
$( w sub 1 (x) ,~ w sub 2 (x))$.
To circumvent this difficulty,
we select $B$ so that the standard
Coppersmith algorithm without the
variation proposed here would generate
about $1.6 ^ | S |$ equations.
(This involves increasing $B$ by at most 1.)
We then implement the present variation,
with the new value of $B$.
Essentially all of the $1.6 ^ | S |$ equations
that would be generated by the standard
Coppersmith algorithm can be generated
by the new variation with appropriate
choices of $v sub 1 (x)$ and $v sub 2 (x)$,
and most can be generated in roughly the
same number of ways.
Hence we can again model this situation
in terms of the ``balls into buckets''
problem described in Section 5.4;
we have about $1.6 ^ | S |$ buckets
corresponding to the equations we can
possibly obtain, and we are throwing
balls into them corresponding to the
equations our variation actually produces.
If we obtain about $1.6 ^ | S |$ equations
all told, approximately $ 1.6 ( 1 -e sup -1 ) ^ | S |$$~>~1.01 ^ | S |$
of them will be distinct, and so it will be
overwhelmingly likely that $| S |$ of them
will be independent.
.P
In our new variation we do not need to check
whether
$( u sub 1 ( x ) ,~ u sub 2 (x) ) ~=~1$,
and thus whether
$( v sub 1 (x),~ v sub 2 (x) )~=~1$.
Therefore we can prepare beforehand
a list of all polynomials of degrees
$<=~B-1$ that are composed of irreducible
factors of degrees
$<=~m$, and this will generate a slight
additional saving over the standard
Coppersmith algorithm.
(In order to take full advantage of the sparse
matrix techniques of Section\ 5.7, it might be
best to use only irreducible factors of degrees
$<= ~m-5$, say.)
The effort needed to compute $u sub 1 (x)$
and $u sub 2 (x)$
(i.e., to solve a small linear system of
equations), which is comparable to the
work needed to test whether a polynomial
has all its irreducible factors of
degrees $<=~m$, can be amortized over
more test polynomials
by requiring that degrees of
$v sub 1 (x)$ and
$v sub 2 (x)$ be $<=~B-2$,
since that will produce at
least 15 nonzero solutions
each time.
.P
There are other ways to speed up
the Coppersmith algorithm.
One way would be
to fix $2B+2-b$ of the coefficients
of $u sub 1 (x)$ and $u sub 2 (x)$,
where $b$ is maximal subject to
being able to store about $2 sup b$
small integers.
Then, for all
irreducible polynomials $u(x)$
of degrees $<=~m$, one could
quickly compute those choices
of the remaining $b$ coefficients
for which $w sub 1 (x)$ or
$w sub 2 (x)$ is divisible by $u(x)$.
All that would need to be stored for
each of the $2 sup b$ combinations
would be the sum of the degrees of
the divisors that were found.
This variation, however, does not
appear as promising as the one discussed
above, and it would require some
very novel architectures to
implement it on a parallel
processing machine of the type
we will discuss later.
Hence we do not explore this variation
further.
.P
A slight improvement on the basic idea of this section is to
allow $v sub 1 (x)$ and $v sub 2 (x)$ to have different degrees,
subject to the requirement that their sum be $<= ~2B-2$, so as
to make the degrees of $w sub 1 (x) / v sub 1 (x)$ and
$w sub 2 (x) / v sub 2 (x)$ more nearly equal.
.P
Another modification to the Coppersmith algorithm was
suggested by Mullin and Vanstone [48].
It consists of choosing $w sub 1 (x)$ to be of the form
.DS 3
.EQ
w sub 1 (x) ~=~ u sub 1 (x) ~x sup h-a ~+~ u sub 2 (x)
.EN
.DE
for $a ~=~ 1$ or 2, say, and selecting
.DS 3
.EQ
w sub 2 (x) ~==~ w sub 1 (x) sup {2 sup k} ~x sup b ~( roman mod ~f(x)) ^,
.EN
.DE
where $b$ is chosen so as to give small degree for $w sub 2 (x)$
after reduction modulo $f(x)$.
This might allow the use of slightly lower degree polynomials
for $u sub 1 (x)$ and $u sub 2 (x)$ than would otherwise be
required, since if $u sub 1 (0) ~=~ 1$, the equations this
method yields ought to be idependent of those the basic method
produces.
This modification can be combined with the others suggested here.
.H 2 "Sparse matrix techniques"
So far we have concentrated on
variations on the linear equation
collection phase of the index-calculus
algorithm.
However, as we noted in Section 4,
the difficulty of solving systems
of linear equations seemed for a long time to
be an important limiting factor
on the algorithm
and affected the asymptotic estimate of its running
time.
For example, in the basic algorithm, if the term $2 sup 2m$
in (4.16) were replaced by $2 sup rm$ for any $r ~>~ 2$
($r~=~ 3$ corresponding to the use of gaussian elimination,
for example), then the minimum of (4.16) would occur not at
$m ~wig~ c sub 1 (n ~ log sub e n ) sup 1/2$, but at a
smaller value, $m ~wig~ c sub 1 ( r) ~(n ~ log sub e n ) sup 1/2$,
and would be larger, with $c sub 2$ replaced by
.DS 3
.EQ
c sub 2 (r) ~=~ r(2(r-1)) sup {- 1/2} ~( log sub e 2) sup 1/2 ~.
.EN
.DE
In this section, though, we will show that the linear
equations produced by the index-calculus algorithm
can be solved in time essentially $| S | sup 2$, where
$| S |$ is roughly the number of equations.
.P
The matrices of coefficients of
the linear equations generated
by the first stage of the
index-calculus algorithm are
special in that they are very
sparse.
The reason is that the coefficient vector of each equation is
obtained by adding several vectors $( b sub v (h))$, indexed
by $v ~epsilon~ S$, coming from factorizations of polynomials
.DS 3
.EQ
h ~=~ prod from {v ~epsilon~ S} ~v sup {b sub v (h)} ~.
.EN
.DE
Since the polynomials $h$ are always of degrees $< ~n$,
there can be at most $n$ nonzero $b sub v (h)$, and so
each equation has at most $n$ nonzero entries.
This is a very small number compared to the total number
of equations, which is around $exp ( n sup 1/3 )$ or
$exp ( n sup 1/2 )$.
The literature on sparse matrix
techniques is immense, as can
be seen by looking at
[4,6,11,27,61] and the
references cited there.
Many of the techniques discussed
there turn out to be very
useful for the index-calculus
problem, even though we face a
somewhat different problem from
the standard one in that we
have to do exact computations
modulo $2 sup n -1$ as opposed
to floating point ones.
In the worst case, the problem of
solving sparse linear systems efficiently
is probably very hard.
For example, it is known that
given a set of $0-1$ vectors
$vun sub 1 , "..." ,~ vun sub r$,
each of which contains exactly
three 1's, to determine whether
there is a subset of them
of a given size that
is dependent modulo 2 is $NP$-complete [35].
Thus we cannot hope to find
the most efficient worst case
algorithm.
However,
very efficient
algorithms can be found.
.P
There are several methods for solving the systems of linear
equations that arise in the index-calculus algorithms that
run in tone $O(N sup {2 + epsilon} )$ for every $epsilon ~>~ 0$,
where $N$ is the number of equations.
The first ones were developed by D. Coppersmith and the author
from an idea of N. K. Karmarkar.
This idea was to adapt some of the iterative algorithms that have
been developed for solving real, symmetric, positive definite
systems of equations [6,11,33,39].
For example, in the original version of the conjugate gradient
method [33], in order to solve the system $A x ~=~ y$, where $A$
is a symmetric positive definite real matrix of size $N$ by $N$, and
$y$ is a given real column vector of length $N$, one can proceed
as follows.
Let $x sub 0$ be an arbitrary vector of length $N$, and let
$P sub 0 ~=~ r sub 0 ~=~ y ~-~ A x sub 0$.
The algorithm then involves $<= ~N-1$ iterations of the following
procedure: given $x sub i , r sub i$, and $p sub i$, let
.DS 3
.EQ (5.15a)
a sub i ~mark =~ {( r sub i , r sub i )} over {( p sub i , A p sub i )} ~,
.EN
.sp
.EQ (5.15b)
x sub i+1 ~lineup =~ x sub i ~+~ a sub i p sub i ~,
.EN
.sp
.EQ (5.15c)
r sub i+1 ~lineup =~ r sub i ~-~ a sub i A p sub i ~,
.EN
.sp
.EQ (5.15d)
b sub i ~lineup =~ {( r sub i+1 , r sub i+1 )} over {( r sub i , r sub i )} ~,
.EN
.sp
.EQ (5.15e)
p sub i+1 ~lineup =~ r sub i+1 ~+~ b sub i p sub i ~.
.EN
.DE
It can be shown [33] that if the computations are done to
infinite precision, the algorithm will find $r sub i ~=~ 0$ for
some $i ~<=~ N-1$, and $x ~=~ y sub i$ will then solve the
original system $A x ~=~ y$.
.P
There are several problems with trying to use the conjugate
gradient method to solve the systems of linear equations
that arise in the index-calculus algorithms.
One is that the system is not symmetric, and one has to solve
$B x ~=~ y$ where $B$ is not even a square matrix.
This problem can be bypassed (as is well known, cf. [33])
by solving the system $A x ~=~ z$, where $A ~=~ B sup T B$ and
$z ~=~ B sup T y$.
Since $B$ will in general be of almost full rank, solutions to
$A x ~=~ z$ will usually give us solutions to $B x ~=~ y$.
The matrix $A$ will not in general be sparse, but its entries
do not have to be computed explicitly, since it is only necessary
to compute the vectors $A p sub i$, and that can be done by
multiplying $p sub i$ first by $B$ and then $B sup T$.
The matrix $B$ can be stored in the sparse form, with rows and
columns being given by lists of positions and values of nonzero
coefficients.
.P
The main difficulty with the use of the conjugate gradient method
is that the basic theory was based on minimizing a quadratic
functional, and this does not apply in finite fields.
However, as was suggested by Karmarkar, the most important property
of the algorithm is that the direction vectors $p sub i$ are mutually
conjugate (i.e., $(p sub i , ~A p sub j ) ~=~ 0$ for $i ~!=~ j$),
and this is a purely algebraic property.
Therefore the algorithm will terminate after at most $n-1$ iterations
and will find a solution unless at some stage a vector $p sub i$ is
encountered such that $(p sub i , ~A p sub i ) ~=~ 0$.
This cannot happen if $A$ is a real positive-definite matrix and
$p sub i ~!=~ 0$, but can occur over finite fields.
If the computations are being done over a large finite field,
the probability of this occurring if $x sub 0$ is choosen at random
is quite low.
If the field is small, say $GF( q)$ with small $q$, this probability
is much more significant, and the way to avoid the problem is to
choose $x sub 0$ to have entries in a larger field, say $GF ( q sup t )$
for some small $t epsilon Z sup +$.
.P
The adaptation of the conjugate gradient algorithm outlined above
has been tested successfully by the author on some small systems.
The advantages of the method include not only speed, since only
about $NQ$ operations in the field $GF( q sup t )$ are required,
where $Q$ is the number of nonzero entries in $B$, and thus
$O( log ~N)$ or $O(( log ~N ) sup 2 )$ in our problems, but
also very modest storage requirements, since aside from the matrix
$B$ it is necessary to store the vectors $x sub i , ~p sub i , ~r sub i$
for only two consecutive values of $i$ at a time.
.P
An algorithm due to Lanczos [39], somewhat different from
the conjugate gradient algorithm, was similarly adapted by Coppersmith
to solve the linear systems arising in the index-calculus
algorithm.
Coppersmith used that method to obtain another solution to the
linear system that arose in the implementation of his attack
on discrete logarithms in $GF( 2 sup 127 )$.
.P
A more elegant method for dealing with the index-calculus linear
systems was invented recently by Wiedemann [66].
Suppose first that we wish to solve for $x$ in $A x ~=~ y$, where
$A$ is a matrix of size $N$ by $N$ (not necessarily symmetric) over
a field $GF (q)$.
Let $v sub 0 , v sub 1 ^,...,^ v sub 2N$ be vectors of length
$K$, which might be 10 or 20, with $v sub j$ consisting of the first
$K$ coefficients of the vector $A sup j y$.
Since to compute the $v sub j$ we need only start with $y$ and
keep multiplying it by $A$, without storing all the vectors
$A sup j y$, we need only $O(KN)$ storage locations, each one
capable of storing an element of $GF( q )$, and the number of
$GF( q )$ operations to carry out this computation is $O(NQ)$.
Now the matrix $A$ satisfies a polynomial equation of degree $<= ~N$:
.DS 3
.EQ (5.16)
sum from j=0 to N ~c sub j A sup j ~=~ 0 ^,
.EN
.DE
and therefore also for any $k ~>=~ 0$,
.DS 3
.EQ (5.17)
sum from j=0 to N ~c sub j A sup j+k y ~=~ 0 ~.
.EN
.DE
Eq.\ (5.17) implies that any single component of the
$v sub 0 ^,...,^ v sub 2N$ satisfies the linear recurrence with
characteristic polynomial
.DS 3
.EQ (5.18)
sum from j=0 to N ~c sub j z sup j ~.
.EN
.DE
Given any sequence of length on the order of $N$, the
Berlekamp-Massey algorithm [29,44,56] finds its minimal
characteristic polynomial in $O( N sup 2 )$ operations in
the field $GF( q )$.
Hence if we apply the Berlekamp-Massey algorithm to each of
the $K$ coordinates of the vectors $v sub 0 ^,...,^ v sub 2N$,
we will in $O(K N sup 2 )$ steps obtain $K$ polynomials whose
least common multiple is likely to be the minimal polynomial
of $A$.
When we do find that minimal polynomial, and it is of the form
(5.18) with $c sub 0 ~!=~ 0$, then we can easily obtain the
desired solution to $A x ~=~ y$ from
.DS 3
.EQ
y ~=~ A sup 0 y ~mark =~ - c sub 0 sup -1 ~sum from j=1 to N ~c sub j
A sup j y
.EN
.sp
.EQ (5.19)
~~~~~~~~~~~~~
.EN
.sp
.EQ
~lineup =~ A left ( - c sub 0 sup -1 ~sum from j=1 to N ~c sub j
A sup j-1 y right ) ~.
.EN
.DE
If $A$ is nonsingular, then $c sub 0 ~!=~ 0$, as is easy to see.
Conversely, if $c sub 0 ~!=~ 0$, then $A$ is nonsingular, since
we can then write
.DS 3
.EQ
A ~sum from j=1 to N ~c sub j A sup j-1 ~=~ - c sub 0 I ~.
.EN
.DE
In general in index-calculus algorithms, we have to solve
a system of the form $A x ~=~ y$, where $A$ is of size $M$ by
$N$, with $M ~>~ N$ (but $M-N$ small).
One way to reduce to the earlier case of a nonsingular square matrix
is to take a submatrix $A prime$ of $A$ of size $N$ by $N$, and
apply the algorithm presented above to $( A prime ) sup T x ~=~ z$ for
some random vector $z$.
If $A prime$ turns out to be nonsingular, we can then go back and
search for solutions to $A prime x ~=~ y$, which is what we are
interested in.
If $A prime$ is singular, though, we will obtain a linear dependency
among the rows of $A prime$.
This means we can discard one of the rows of $A prime$ that was
involved in that dependency and replace it with another row of that
part of $A$ that has not been used yet.
After a few steps, we ought to obtain a nonsingular $A prime$, and
this will enable us to solve for $x$ in $A x ~=~ y$.
Wiedemann [66] also has a deterministic algorithm, which may not
be as practical, however.
.P
We conclude this section by discussing some very simple methods
for solving sparse systems of equations.
Some of these methods can be used as a preliminary step before
the application of Wiedemann's algorithm, say, since they serve
to reduce the effective size of the matrix that has to be dealt
with.
In some cases these
methods by themselves
could be just about as efficient as the
techniques described above.
These methods are based
on a simple observation that has
often been made in the work on
sparse matrices (cf. [6]), namely
that if a matrix is noticeably
sparser on one end than on the
other, then it is better to start
gaussian elimination from the
sparse end.
In our case, if we arrange the
matrix of coefficients so
that the columns correspond
to polynomials $v~member~S$
sorted by increasing degree,
then the right side of the matrix
will be very sparse.
(If we use the fast version
for generating the $h sup *$
that is presented in Section 5.3,
it is necessary to choose the
random $v sub r ~member~S$ to
have only low degrees for this
to remain true.)
To see just how sparse that matrix is, consider the
Coppersmith algorithm in $GF(2 sup n )$, with $k, ~m$,
and $B$ chosen to satisfy (4.34a-c) with $alpha$
satisfying (4.38), and $beta$ and $gamma$ satisfying
$beta ~=~ gamma$ and (4.40).
If we take $M ~wig~ m sup -1 2 sup m$, then the matrix
of coefficients will have about $2M$ rows and $2M$ columns,
with columns $M+1 ,..., 2M$ (approximately) corresponding
to the irreducible polynomials of degree $m$.
We now consider those columns.
Any row in the matrix comes from adding two vectors
of discrete logarithm coefficients from factorization
of two polynomials of degrees about $B ^ cdot ^ 2 sup k$,
both of which are divisible only by irreducible factors of
degrees $<= m$.
The probability that a polynomial of degree $B ^ cdot ^ 2 sup k$,
which factors into irreducibles of degrees $<= m$, also
is divisible by a particular chosen irreducible polynomial
of degree exactly $m$ is approximately
.DS 3
.EQ
{2 sup -m ^ p(B 2 sup k ^ - ^ m,m)} over {p(B 2 sup k , m)} ^,
.EN
.DE
which, by Lemma A.3 of Appendix A, is
.DS 3
.EQ
wig ~ 2 sup -m ^ m sup -1 B 2 sup k roman log (B2 sup k /m) ^.
.EN
.DE
Therefore the probability that any particular entry
in the last $M$ columns of the matrix is nonzero is about
.DS 3
.EQ (5.20)
2 sup -(m-1) ^ m sup -1 B 2 sup k roman log (B2 sup k /m ) ^.
.EN
.DE
(The factor 2 comes from the fact that we are adding two
vectors.)
For the choices of $B, ^ 2 sup k$, and $m$ that were specified,
this becomes $delta M sup -1$, where
.DS 3
.EQ
delta ~=~ 2 alpha gamma beta sup -2 /3 ~=~ 2 beta sup -3/2 /3 ~=~ roman log
~2 ~=~ 0.6931....
.EN
.DE
(Exactly the same asymptotic result also applies to the
basic index-calculus algorithm.)
Therefore, by the ``balls into buckets'' model, we expect
that with probability about
.DS 3
.EQ
(1- delta M sup -1 ) sup 2M ~approx~ roman exp (-2 delta ) ~=~ 1/4 ^,
.EN
.DE
any column among the last $M$ will contain only zeros.
This means that about $M/4$ of the $M$ irreducible
polynomials of degree $m$ will not appear in any of
the factorizations and so
the data base obtained from the
first phase will be missing those values.
More importantly, it means that it was not necessary
to obtain all of the $2M$ equations, as $7M/4$ would
have sufficed.
(In fact fewer than $7M/4$, since with that few equations,
the chances of obtaining a zero column would be even
larger, and in addition we would also have some irreducible
polynomials of degrees $m-1 , ^ m-2$, etc., which would
not appear in the equations.)
In addition, the probability of a particular column among
the last $M$ having just a single nonzero coefficient
is about
.DS 3
.EQ
2M ^ cdot ^ delta M sup -1 (1- delta M sup -1 ) sup 2M-1 ~approx~
2 delta ~roman exp (-2 delta ) ^ = ^ ( roman log ~ 2 )/2 ^ = ^ 0.346...
.EN
.DE
Thus an additional 0.346M of the last $M$ columns would
have a single nonzero coefficient, so that we could
remove those columns together with the rows in which
those columns have nonzero coefficients, solve the
remaining system, and then obtain the values of logarithms
corresponding to the deleted columns by back substitution.
(Occasionally a row might contain two nonzero coefficients
which are the only such in their columns, which would
prevent recovery of the values of the corresponding logarithms,
but that is not a significant problem.)
Furthermore, removal of those rows and columns would create
more columns with only a single nonzero coefficient,
so that the size of the matrix could be cut down by more
than 0.35M.
However, both simulations and heuristic arguments show that
if we proceed to carry out standard gaussian elimination, proceeding
from the sparse end, then very rapid fill-in occurs.
Therefore one does have to be careful about algorithms that are used.
.P
The above discussion of just how sparse the index-calculus algorithms
matrices are was meant to motivate the following method.
It will be helpful to explain it in terms of operating on the full
matrix, although in practice the matrix would be stored in the sparse
encoding, using lists of nonzero coefficients and their positions
for rows and columns, just as in the case of the algorithms discussed
above.
The algorithm is as follows:
.VL 10
.I
.LI "Step 1:"
Delete all columns which have a single nonzero coefficient and
the rows in which those columns have nonzero coefficients.
.LE
.R
Step 1 is repeated until there are no more columns with a single
nonzero entry.
.VL 10
.I
.LI "Step 2:"
Select those $alpha M$ columns which have the largest number of
nonzero elements for some $alpha ~>~ 0$.
Call these columns "heavy," the others "light."
.LE
.R
A typical value of $alpha$ might be 1/32.
The entries in the "heavy" columns for every given row might be
stored on a disk, with a pointer attached to the row list
indicating the storage location.
These pointers would have coefficients attached to them, which
are set to 1 initially.
The weight of a row is then defined as the number of nonzero
coefficients in its "light" columns.
.VL 10
.I
.LI "Step 3:"
Eliminate variables corresponding to rows of weight 1 by subtracting
appropriate multiples of those rows from other rows that have
nonzero coefficients corresponding to those variables.
.LE
.R
During execution of Step 3, if $u$ times row $i$ is to be subtracted
from row $j$, the pointers attached to row $j$ are to have added
to them the pointers of row $i$, with their coefficients multiplied
by $u$.
Step 3 is to be repeated until there are no more rows of weight 1.
At the end of this process there are likely to be many more
equations than unknowns.
We can then perform the following operation.
.VL 10
.I
.LI "Step 4:"
If $r$ rows are excess, drop the $r$ rows with highest weight.
.LE
.R
We now iterate Step 1, and then Step 3.
We then go on to the next procedure.
Note that if a variable indexed by $j$, say, appears in
rows of weights $2 <= w sub 1 ~<=~ w sub 2 ^ <= ... <= ^ w sub k$,
then eliminating that variable using a row of weight $w sub i$
will increase the number of nonzero entries in the matrix (after
deletion of the row of weight $w sub i$ and the column corresponding
to our variable) by
.DS 3
.EQ (5.21)
(w sub i -1) (k-1) ~-~ w sub i ~-~ (k-1) ~=~ ( w sub i -2) (k-1) ~-~ w sub
i ~.
.EN
.DE
Hence to minimize the amount of fill-in, we need to choose that
variable and that $w sub i$ (which clearly equals $w sub 1$) for which
(5.21) is minimized.
Keeping track of this quantity is fairly easy if we use a priority
queue data structure.
.VL 10
.I
.LI "Step 5:"
Eliminate that variable which causes the least amount of fill-in.
.LE
.R
.P
The algorithm outlined above can be implemented to run very
fast, and it reduces the problem of solving a roughly $2M$
by $2M$ system to that of solving an $alpha M$ by $alpha M$ system.
What is perhaps most remarkable, if the original system is
sufficiently sparse, only the first few steps of the algorithm
are needed.
For example, if the elements of the matrix are chosen
independently at random, so that the probability of an entry
in the last $M$ columns being nonzero is $delta M sup -1$, in the next
$M/2$ column is $2 delta M sup -1$, etc., where $delta ~<=~ 0.85$
(compared to $delta ~=~ 0.693...$ for the optimal case of
Coppersmith's algorithm), and $alpha ~=~ 1/32$, than Steps 1-4
of the algorithm are all that is needed, since by the time they are
completed, there is nothing left of the "light" portion of the matrix.
This result is confirmed by simulations (with systems of sizes up
to 96,000) and by heuristic arguments.
.P
The method presented above draws on ideas that are well known
in the literature on sparse matrices (cf. [11]).
Moreover, some of these ideas have already been used in the
factoring integers and computing discrete logarithms.
For example, J. Davenport in his computations related to Coppersmith's
algorithm [19] used some heuristic methods to minimize fill-in.
Such methods were also used
during the execution of the Blake et al.\ [8]
version of the basic index-calculus algorithm in
$GF(2 sup 127 )$.
According to R. Mullin (private communication), the
system of about 16,500 equations in about that many
variables ($m=17$ was used) was reduced by methods
similar to those presented above to a system of size under 1000,
which was then solved by ordinary gaussian elimination.
Moreover, their procedure did not involve such tricks
as always choosing the equation with fewest nonzero
entries during elimination, which appear to result
in dramatic improvements in performance.
Therefore we expect these methods to be quite useful.
.H 1 "Practical and impractical implementations"
Blake, Fuji-Hara, Mullin, and Vanstone [8]
have successfully tested the basic index-calculus
algorithm on fields up to
$GF ( 2 sup 127 )$.
They estimated that with their VAX 11/780,
a relatively slow minicomputer, it
would have taken them many CPU months to
carry out the first stage of the algorithm
for $GF (2 sup 127 )$ with $m~=~17$.
On the HEP, a powerful multiprocessor
to which they obtained access,
their implementation
of the algorithm took about 8 hours
for the first stage,
of which about one hour was devoted to solving
linear equations.
(Their systematic equations method produced
a substantial fraction of all the required equations.)
Once the first stage is completed,
the second stage is expected to take
around 1 CPU hour per logarithm
even on the VAX 11/780.
On the IBM 3081K, Coppersmith estimated
that the equation collecting phase for $GF ( 2 sup 127 )$ would
take around 9 hours with the basic algorithm.
Using his own variation, Coppersmith was
able to find all the necessary polynomials
(for $m~=~12$) in 11 minutes [19].
(The factorization of the polynomials
to obtain the actual equations took 8
minutes, and solution of the equations
took 20 minutes, but these tasks were
performed with a general purpose symbolic
manipulation program, and so could
undoubtedly be speeded up very substantially.)
Further speedups, perhaps by a factor of
30 to 50, could be obtained by combining
the variation proposed in Section 5.6,
which might gain a factor of 10 to 20,
with those of sections 5.4 and 5.5, which
together might gain a factor of 2 or 3.
Using the Cray-1 might gain an additional
factor of 10 or so, because it is perhaps
5 times faster than the IBM 3081K and
because it could store and manipulate the
test polynomials (of degrees $<wig~42$)
in single words.
Thus we can expect that with current
supercomputers the equation collecting
part of the first phase of the algorithm
can be completed in around one second.
Since the database produced by the algorithm
is not very large (16,510 127-bit numbers
for $m~=~17$ in the basic algorithm and
747 numbers for $m~=~12$ in the Coppersmith
variation), this means that individual
logarithms in $GF ( 2 sup 127 )$ can now
be computed even on personal computers.
Therefore $GF ( 2 sup 127 )$ ought to
be regarded as completely unsuitable for
cryptographic applications.
Our intention here is to explore
what other fields might be appropriate.
.P
We first consider the basic algorithm.
Although it has been made obsolete
by the Coppersmith variation in
applications to the fields $GF ( 2 sup n )$,
it is worth analyzing in detail, since
by comparing our estimates to actual running times we will
obtain a better idea of how accurate the estimates are.
.P
In Section 5 we presented briefly
a number of variations on the
basic index-calculus algorithm.
These variations were not analyzed
very carefully, since we were
interested only in the order of
magnitude of the improvements that
can be obtained from such techniques.
The general conclusion to be drawn
from that section is that the time
to generate the pairs
$( w sub 1 ,~ w sub 2 )$, can probably
be neglected.
The work needed to obtain $| S |$
equations is probably no more than
and at least 1/5 of the work needed
to test
.DS 2
.EQ
| S | ~p ( [n/2] ,~ m ) sup -2
.EN
.DE
pairs $( w sub 1 ,~ w sub 2 )$
by the procedure outlined in
Section 4.3 to see whether all
the irreducible factors of
each of the $w sub i$ are in $S$.
To test each $w sub i$ takes about
$m/2$ operations of the form
(4.8), each of which involves
a squaring modulo a polynomial
of degree perhaps $n/3$ on
average (since the degrees of the $w sup (i) (x)$
will be decreasing, especially if we
use the early abort strategy with
additional test along the way to
discard pairs $( w sub 1 ,~ w sub 2 )$
that are not factoring satisfactorily),
a greatest common divisor operation or
two polynomials of degrees around
$n/3$, and a division, which will
usually be trivial.
.P
To evaluate the significance of the
index-calculus algorithm for
cryptographic schemes, we have t