Computer Science Journal of Moldova, vol.11, no.

2(32), 2003

Finite fields and cryptology

Ennio Cortellini

Abstract
The problem of a computationally feasible method of find-
ing the discrete logarithm in a (large) finite field is discussed,
presenting the main algorithms in this direction. Some crypto-
graphic schemes based on the discrete logarithm are presented.
Finally, the theory of linear recurring sequences is outlined, in
relation to its applications in cryptology.
Keywords: finite field, discrete logarithm, encryption, sig-
nature.

1 Finite fields and discrete logarithms

We review some well-known facts about finite fields.
- For any finite field F , there exist a prime p and a positive integer
n such that F has pn elements. The prime p is the characteristic of F .
- Conversely, for any prime p and a positive integer n there is a finite
field with q = pn elements and this field is unique up to isomorphism.
Such a field is denoted by Fq . For any a ∈ Fq∗ , aq−1 = 1 by the Theorem
of Lagrange from group theory.
- Let Fq be a finite field and Ω its algebraic closure. Then, for any
n
positive integer n, the splitting field of the polynomial X q − X over
Fq is the unique subfield of Ω with q n elements. Moreover,

Fqm ⊆ Fqn

if and only if m divides n. Thus, the lattice of the subfields of Ω

containing Fq is isomorphic to the lattice of the nonnegative integers
ordered by divisibility.
c
°2003 by E. Cortellini

150
 Finite fields and cryptology

- For any prime p, Fp is simply the field ZZp = {b 0, b

1, ..., pd
− 1} of
integers modulo p. In order to construct a field Fq , with q = pn , it is
enough to find an irreducible polynomial g of degree n in ZZp [X], the
ring of univariate polynomials with coefficients in ZZp . Then Fq can be
taken as the factor ring ZZp [X]/(g) (which is actually a field).
- Fq∗ = Fq \{0} is a multiplicative group, which is cyclic. A generator
of Fq∗ is called a primitive element of Fq . This simple fact plays a major
role in what follows. A polynomial g of degree n in Fq [X] is called
primitive if it is the minimal polynomial of a primitive element of Fqn .
We fix a prime p and q = pt , with t a positive integer.
1.1 Definition. Let b a primitive element of Fq . Then every a ∈ Fq∗
can be written uniquely as
a = br ,
where r is an integer with 0 ≤ r ≤ q − 2, called the discrete logarithm
of a in base b and denoted by logb (a) (sometimes also called the index
of a relative to b and denoted indb a).
1.2 Remark. The discrete logarithm can be defined in any finite
cyclic group G (its operation written multiplicatively). Let b be a
generator of G and n = |G| the order of b. For any a ∈ G, there exists
a unique integer r with 0 ≤ r ≤ n − 1 such that a = br (r is called the
discrete logarithm of a in base b and is denoted logb a).
When b and a as above are given, the task of computationally de-
termining logb (a) is known as the discrete logarithm problem (DLP)
and it is presumed to be difficult if n is large. Let w = [log2 n] + 1
(the number of bits needed to represent n). The classical algorithm of
exponentiation using the base 2 expansion of r computes br from b and
r in at most 2w multiplications in G, so taking powers is of O(w) time.
On the other hand, finding logb (a) by an exhaustive search (i.e.,
compute all powers of b until a is found) takes at most ord(b) multipli-
cations and equality checks. In the direction of finding lower bounds
for the running time of the DLP solving algorithms, Shoup [32] has
shown that any ”generic” probabilistic algorithm for finding with high
probability the discrete logarithm in the cyclic group ZZN (i.e., which
does not use any special properties of the group other than the fact
that each group element is encoded as a unique binary string) must

151
 E. Cortellini

perform at least cp1/2 group operations, where p is the largest prime

dividing N and c is a constant. So any generic DLP algorithm takes at
least O(2w/2 ) = O(n1/2 ) steps, which can be made prohibitively large
if w is large. While the hardness of the DLP is not entirely proven,
the prevailing opinion is that discrete logarithm based cryptographic
systems are secure enough if implemented appropriately.

2 Algorithms for determining the discrete

logarithm
We give some facts on the computation of the discrete logarithm in Fq .
If m and n are integers, with n > 0, we denote by m mod n the positive
remainder of m when divided by n. So, m mod n ∈ {0, 1, ..., n − 1}.
2.1 Proposition. Suppose that, given a prime p, q = pt , b a
primitive element of Fq∗ and a ∈ Fq∗ , there exists an algorithm DLp
which outputs logb (a)mod p. Then there is an algorithm which finds
logb (a).
Proof. Let r = logb (a). Then r is written uniquely as:
r = x0 + x1 p + ... + xt−1 pt−1 , with xi ∈ {0, ..., p − 1}.
The xi are the digits of r in its development in base p. Thus, r mod
p = x0 can be determined by the algorithm DLp . We can find now
x1 by applying DLp to b(r−x0 )/p =: r1 . But b(r−x0 )/p = (br b−x0 )q/p =
(ab−x0 )q/p and one easily sees that all computations in the last expres-
sion are feasible. The process is now applied to r1 . Continuing in this
way, one obtains succesively x1 , ..., xt−1 , which yield logb (a).
2.2 Remark. In [18], Mullen and White prove the following ex-
plicit formula for logb (a) mod p:
q−2
X
logb (a) ≡ −1 + aj (b−j − 1)−1 (mod p).
j=1

The formula is valid for any q = pt with q ≥ 3 and any a ∈ Fq∗ . But
the ways (if any) to apply this formula to an efficient computation of
logb (a) for large q are unknown.

152
 Finite fields and cryptology

2.3 There is an efficient algorithm to compute the discrete algo-

rithm in Fq if q − 1 decomposes in a product of small primes (the
Pohlig Hellman algorithm). With the notations above, r = logb (a) is
smaller than q − 1, so r = r mod(q − 1). Suppose q − 1 = q1 ...qk , where
qi is a power of a prime pi and the pi ’s are distinct, for 1 ≤ i ≤ k. By
the Chinese Remainder Theorem, r mod(q − 1) can be uniquely found
if r mod qi are known for 1 ≤ i ≤ k. Furthermore, as shown in the
preceding proposition, computing r mod qi amounts to computing r
mod pi . Let si = r mod pi . Then

a(q−1)/pi = br(q−1)/pi = cri ,

where ci = b(q−1)/pi is an element of Fq∗ of order pi . So cri = csi i and

thus si can be uniquely determined from csi i . To make this task easier,
a list of the powers of ci can be precomputed and si read from the list.
Moreover, the baby step - giant step method (see below) can be used
in this stage for recovering the r from the list.
Obviously, this procedure is of practical value only if the pi ’s are
small. For details, see Pohlig and Hellman [1], McCurley [12].
The Pohlig Hellman method can be easily generalized to an arbi-
trary cyclic finite group G satisfying some natural computational prop-
erties. Thus, the method reduces the DLP problem in a general group
to the case of groups of prime power order.
2.4 Shanks’ [28] ”baby step - giant step” method uses a time-
memory trade off algorithm (it uses a large amount of memory to cut
down the time it would normally take to solve the problem). It is a
deterministic algorithm, devised initially to compute ideal class num-
bers of quadratic number fields. We present a version of the algorithm
that works in any finite cyclic group G (more generally, if in a finite
group G, the elements g and a are such that a belongs to the subgroup
generated by g, the method determines an integer x such that a = g x ).
Let g, a ∈ G with n = ordg, such that a = g r for some r ∈
{0, ..., n − 1} that we want to find. Assume that the set of the com-
puter representations of the elements of G is totally ordered and can
be ordered efficiently. Let m = [n1/2 ].
Step 1. Compute g mj , for j = 0, ..., m − 1. (the ”giant steps”)

153
 E. Cortellini

Step 2. Sort the pairs (g mj , j), j = 0, ..., m−1 by the first coordinate
and store them in a list GS.
Step 3. Compute ag −i for i = 0, ..., m − 1. When doing this, for
every i check if ag −i = 1. If this is the case, set x = i and stop.
Otherwise, we end up with a table BS (the ”baby steps”) with entries
(ag −i , i), i = 0, ..., m − 1.
Step 4: Sort the list BS by the first coordinate.
Step 5: Find a pair in each list with the same first coordinate, i.e.,
(y, j) in BS and (y, i) in GS. So we have y = g mj = ag −i , i.e. a = g mj+i .
Step 6: Set r = mj + i.
There certainly is a match in step 5, since the list BS contains m
consecutive powers of g and GS contains all powers of g that have
exponent a multiple of m.
Observe that steps 1 and 2 are independent of a so they can be
regarded as a precomputation. Alternatively, one can begin with steps
3 (and 4 if necessary) and proceed with step 1, checking for every j if
there is some i such that (g mj , i) belongs to the list BS (easily done if
BS is ordered). This avoids storing the list GS, but the computation
of the g mj ’s has to be done again for every input a.
If r ≥ n, the algorithm uses one inversion and m+[n/m]+O(log2 m)
multiplications. It uses m (or 2m if GS is precomputed) locations for
storing group elements and [n/m] table look-ups in a table of size m.
Some variants of the baby-step giant-step method have been pro-
posed, based on a dynamic increase of the giant step size (so the giant
steps cannot be performed before the baby steps, as they depend dy-
namically on them). In Adleman [1], the step size is doubled at certain
intervals. In Terr [34], the method increases the giant step size af-
ter each baby step and is based on a representation of integers using
triangle numbers.
Although (in √ theory) in this method the running time is reduced
by a factor of 2, in practice it performs equally well as the original
method. Also, in a worst case scenario (i.e. r is close to n), the original
method requires less group operations than the modified versions. For
a discussion of the efficiency of various baby step - giant step methods,
depending on the probability distribution for the solution r on the set

154
 Finite fields and cryptology

of positive integers, see Teske [35].

2.5 Another case in which a computationally feasible method of
determining the discrete logarithm is available is when q is either a
prime or a power of a small prime. Of course, it is of interest when q
is large. The ideas go back to Western and Miller [40] and Miller [19].
The algorithm appears in Adleman [1], Merkle [18], and Pollard [27].
We sketch the algorithm here.
The method (the index-calculus algorithm) depends on the initial
choice of a set {a1 , ..., ak } ⊆ Fq∗ . Given a1 , ..., ak , one then seeks for a
set of m identities of the following type:
k
Y eij
aj = bfi , 1 ≤ i ≤ m. (1)
j=1

where eij and fi are integers. These identities are equivalent to the
following system of congruences mod q − 1:
k
X
eij logb (aj ) ≡ fi (mod q − 1) , 1 ≤ i ≤ m.
j=1

The eij should be chosen such that the system above (with the un-
knowns logb (aj)) has a unique solution mod q − 1 and thus logb (aj ) can
be found.
With the a1 , ..., ak and their discrete logarithms prepared as above
(this is done only once for the given field Fq ), the method computes
the discrete logarithm logb (a) by constructing an identity of the form:
k
Y hj
aj = abf . (2)
j=1

Since a = br , where r = logb (a), this is equivalent to

k
X
r≡ hj logb (aj ) − f (mod q − 1),
j=1

which gives r = logb (a).

155
 E. Cortellini

There remains the problem of describing a method for the selection

of the system a1 , ..., ak and how to find the identities (1) and (2). If q is
prime, one chooses a1 , ..., ak to be small primes and the identities (1) are
taken to be the decomposition of integers in prime factors. In practice,
one way to obtain such identities would be to compute some powers
of b, select those that are small and take the canonical factorization of
these powers into primes (in this way, the fi ’s are known in advance
and the eij ’s will be given by factorizing into primes). For an efficient
computation, it seems that a probabilistic algorithm is the only suitable
alternative in determining the identities (1) and (2). Details can be
found in McCurley [12], Odlyzko [24], Lidl and Niederreiter [13].
Coppersmith [6], [7] has devised a probabilistic variant of the index-
calculus algorithm for computing the discrete logarithm in the case
q = 2t . It was shown (under some assumptions) to have a complexity
of O(exp(ct1/3 log(t2/3 ))), for some positive constant c, which is sig-
nificantly better than O(exp(t1/2 )) for the basic version; but it does
not apply to finite fields with characteristic other than two. A detailed
analysis of the Coppersmith algorithm is made by Odlyzko [24].
2.6 Pollard’s rho method [27], generalized by Teske [36], [37], can
be applied in determining discrete logarithms in any cyclic group (G, ∗)
with generator g, provided G satisfies the following computational con-
ditions:
- Given any two elements g, h ∈ G, their product g ∗ h can be
computed in G.
- Given any two elements g, h ∈ G, one can decide if g = h.
- Given a ”small” integer r (originally Pollard assumed r = 3), one
can find r disjoint subsets T1 , ..., Tr whose union is G, of roughly equal
size; moreover, given any group element we can check to which of these
sets it belongs.
The method uses an initially chosen function (the ”iterating func-
tion”) ϕ : G → G and a starting value y = y0 ∈ G. Then it computes
the sequence (yk )k ≥ 0, where yk+1 = ϕ(yk ), for any k ≥ 0.
Since G is finite, there exist two uniquely determined smallest in-
tegers λ ≥ 1 and µ ≥ 0 such that yk+λ = yk , for all k ≥ µ. Thus, the
sequence yk is periodic for k ≥ µ (λ is called the period of yk and µ is

156
 Finite fields and cryptology

the preperiod of yk ). The name rho method comes from the fact that,
when drawing the succesive terms of yk starting from the bottom of
the paper, the terms yk with k < µ are arranged in a vertical line and
the terms yk with k ≥ µ form a cycle; thus one gets a picture similar
to the Greek letter ρ (rho).
Since the Pohlig and Hellman method allows the reduction to the
prime power order, we may suppose that |G| = p, a prime integer. Here
is the rho method of solving the DLP in G, described using the original
Pollard iterating function. Let g be a generator of G and h ∈ H; we
want to find x = logg h.
Pollard’s original iterating function ϕ (adapted to this case) is de-
fined as follows: divide G into 3 pairwise disjoint sets T1 , T2 , T3 of about
the same size and define, for any y ∈ G:


 g ∗ y,y ∈ T1
ϕ (y) = y2 ,
y ∈ T2

 h ∗ y, y ∈ T
3

Choose a random integer α ∈ {0, ..., p − 1} and set y0 = g α , yk+1 =

ϕ(yk ), for any k ≥ 0. Thus, there exist two sequences (αi ) and (βi ) in
ZZp such that yi = g αi ∗ hβi , for i ≥ 0. These sequences satisfy:

α0 = α; β0 = 0;

αi+1 = αi + 1 and βi+1 = βi or

αi+1 = 2αi and βi+1 = 2βi or

αi+1 = αi and βi+1 = βi + 1,

depending on the three cases in the definition of ϕ.
One tries to find a match, i.e. a pair (i, j) with yi = yj and i < j.
There are efficient methods to do this (e.g. Brent [3], Schnorr and
Lenstra [30]). Once we found a match, g αj −αi = hβj −βi = g x(βj −βi ) , so
we get the equation in ZZp :

αj − αi = x(βj − βi ).

157
 E. Cortellini

So x = logg h is given by solving the equation above, if gcd(βj − βi , p) =

1. If this is not the case, choose another α and start over again, but
this is very rare for large p.
If the iterating function ϕ is chosen randomly among the |G||G| func-
tions
p from G to G,p then the expected value for λ + µ is approximately
π|G|/2 ≈ 1.253 |G|.
The space requirements of algorithms using the rho method are
negligible, so in this respect this method is superior to Shanks’ baby
step - giant step method that has roughly the same run time.

3 Cryptographic systems based on the discrete

logarithm problem
On the assumption of the difficulty of the DLP some cryptographic
systems have been proposed.
3.1 The Diffie-Hellman key agreement protocol (also called exponen-
tial key agreement) was developed by Diffie and Hellman [8] in 1976.
The protocol allows two users to exchange a secret key over an insecure
medium without any prior secrets.
The protocol has two parameters: q (a power of a prime number)
and g (a primitive element of Fq∗ , also called a generator). Parameters
g and q are public.
If the users A and B want to agree on a shared secret key, they
proceed as follows. First, A generates a random private value a and B
generates a random private value b, with a and b ∈ {2, ..., q − 2}. Then
they derive their public keys (which are elements of Fq∗ ): A’s public key
is g a and B’s public key is g b . The public keys are exchanged between
A and B. The common secret key is then k = g ab , which A computes
as (g b )a , and B computes as (g a )b .
The protocol assumes that it is computationally infeasible to calcu-
late the shared secret key k = g ab , given the two public values g a and
g b , when q is sufficiently large. Maurer [15] has shown that breaking
the Diffie-Hellman protocol is equivalent to computing discrete loga-
rithms under certain assumptions, i.e. the only way for an attacker to

158
 Finite fields and cryptology

compute the secret key g ab would be to compute a from g a or b from

gb.
3.2 The ElGamal system is a public-key cryptosystem based on
the discrete logarithm problem. It consists of encryption and signature
algorithms. The encryption algorithm is based on the same ideas found
in the Diffie-Hellman key agreement protocol.
As above, q (a power of a prime number) and a primitive element g
of Fq∗ are public. A has a private key a and a public key y (2 ≤ a ≤ q−2,
y ∈ Fq∗ ), where y = g a . Suppose B wishes to send a message m
(m ∈ Fq∗ ) to A. B chooses randomly k with 2 ≤ k ≤ q − 2 and
computes in Fq∗
y1 = g k and y2 = my k .
B then sends (y1 , y2 ) to A. We have

m = (mg ak )g −ak = y2 (g −k )a = y2 (y1−1 )a .

So, after receiving the ciphertext (y1 , y2 ), A can recover the message
m as:
m = (y1−1 )a y2 .

A variant of this protocol is as follows: if the elements in Fq∗ are

represented as words of w bits, y2 above can be replaced by y2 = m
XOR y k , where XOR denotes the bitwise ”exclusive or” between the
words of w bits. In this case, m can be computed by A as m = y2 XOR
y1a .
We describe now the ElGamal signature algorithm.
User A, who wishes to sign messages electronically, publishes a
prime power q, a primitive root g ∈ Fq∗ , and an integer y, 1 ≤ y ≤ q − 2,
which is generated by choosing a random integer a, which is kept secret,
and setting y = g a . The prime power q 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 ∈ Fq∗ , user A provides a pair of integers
(r, s), 1 ≤ r, s ≤ q − 2, such that

gm = y r rs .

159
 E. Cortellini

To generate r and s, user A chooses a random integer k with

gcd(k, q − 1) = 1 and computes r = g k . Since y = g a , this means
that s has to satisfy
g m = g ar+ks ,
which is equivalent to m ≡ ar + ks (mod q − 1). Since gcd(k, q − 1) = 1,
this equation has a unique solution modulo q − 1, and this solution is
easy to find for 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.
The ElGamal signature algorithm is similar to the encryption al-
gorithm in that the public key and private key have the same form;
however, encryption is not the same as signature verification, nor is
decryption the same as signature creation (as in the Rivest-Shamir-
Adleman (RSA) system, for example).
The U.S. National Institute of Standards and Technology (NIST)
has established the Digital Signature Standard (DSS), which is based
on a variant of the ElGamal signature algorithm above, to be the dig-
ital authentication standard of the U.S. government. Here is a brief
description of the principles of the Digital Signature Algorithm (DSA),
according to [33]. The algorithm has the following parameters:
- a 512-bit prime p such that the DLP in Fp∗ is intractable and p − 1
has a prime divisor q which has 160 bits;
- an element g of order q in Fp∗ .
Assume user A has a secret key a Fp∗ . The user A publishes g a =
b ∈ Fp∗ . When A wishes to sign a message m ∈ Fp∗ , A randomly chooses
k ∈ ZZq and computes the pair (γ, δ) ∈ ZZq × ZZq , where:

γ = g k (mod q), δ = (m + aγ)k −1 (mod q)

Since g has order q in Fp∗ , g k is well defined in Fp∗ . The pair (γ, δ)
is then appended to the message m. The receiver of the message can
now verify the authenticity of the message m by checking that
−1
γ = (g m · bγ )δ (mod q)

160
 Finite fields and cryptology

For a detailed description of DSA, see [21].

3.3 Another system that uses exponentiation in finite fields to trans-
mit information is based on an idea due to Shamir ([11] pp. 345-346)
and Massey and Omura [39]. For example, suppose user A wishes
to send a message m (where m is a nonzero element of the pub-
licly known field Fq ) to user B. Then A chooses a random integer
c, 1 ≤ c ≤ q − 1, (c, q − 1) = 1, and transmits x = mc to B. User B then
chooses a random integer d, 1 ≤ d ≤ q − 1, (d, q − 1) = 1, and transmits
0
y = xd = mcd to A. User A now forms z = y c , where cc0 ≡ 1 (mod
q − 1), and transmits z to B. Since
0 0
z = y c = mcdc = md ,
0
B only has to compute z d to recover m, where dd0 ≡ 1 (mod q − 1),
0 0
since z d = mdd = m.
In this scheme it is again clear that an efficient method for com-
puting discrete logarithms over Fq would enable a cryptanalyst to re-
cover the plaintext message m from the transmitted ciphertext mes-
sages mc , mcd , and md .
Finally, we mention that the ability to compute quantities general-
izing discrete logarithms in rings of integers modulo composite integers
would lead to efficient integer factorization algorithms ([2], [14]). This
shows that, in a way, the RSA cryptosystem (based on the difficulty
of factoring large integers) and the discrete logarithm based cryptosys-
tems are roughly equally hard to break.

4 Alternatives to the finite field DLP

In view of the progress of the algorithms dedicated to the DLP in groups
of type Fq∗ , other groups have been proposed for use in cryptographic
applications: ideal class groups of algebraic number fields (see e.g. [5])
or the group of rational points on an elliptic curve over a finite field
(for an introduction, see [10]).
The known methods for computing general elliptic curve discrete
logarithms are less efficient than those for computing discrete loga-
rithms in finite fields. As a result, shorter key sizes can be used to

161
 E. Cortellini

achieve the same security of public-key cryptosystems, which might

lead to better memory requirements and improved performance. The
ElGamal, DSA, and Diffie-Hellman schemes can easily be adapted
to construct elliptic curve encryption, signature, and key agreement
schemes. These variants seem to offer certain implementation advan-
tages over the original schemes, and consequently they draw increasing
attention from the academic community and the industry. For more
information on elliptic curve cryptosystems, see the survey articles [17]
or [29].
Another idea that generalizes the DLP is based on the theory of the
linear recurring sequences in a finite field Fq . We present the basic ideas
of the theory, which also applies to the generation of pseudorandom
sequences.
A sequence (sn )n≥0 of elements of Fq is called a linear recurring
sequence (LRS) of order k if there exist a0 , ..., ak−1 ∈ Fq such that

(∗) sn+k = a0 sn + ... + ak−1 sn+k−1 , ∀n ≥ 0.

Such a sequence (abbreviated (sn )) is also called a linear feedback

shift register sequence, since these sequences are generated by hardware
devices known as linear feedback shift registers.
For instance, the sequence (g r )r≥0 that appears in the DLP (where
g is a primitive element of Fq ) is a linear recurring sequence in Fq of
order 1.
For a given LRS (sn ) of order k, define the state vectors

sn = (sn , ..., sn+k−1 ) ∈ Fqk , ∀n ≥ 0.

To the sequence (sn ) is associated the following k × k characteristic

matrix (which is also the companion matrix of f ):
 
0 0 ... 0 a0
 1 0 ... 0 a1 
 
 
A= 0 1 ... 0 a2  ∈ Mk (Fq ).
 
 .. .. .. .. 
 . . . . 
0 0 ... 1 ak−1

162
 Finite fields and cryptology

The recurrence relation (*) is easily seen to be equivalent with:

sn = s0 An , ∀n ≥ 0.

This relation enables the efficient computation of arbitrary terms of

(sn ) by computing An ; the standard exponentiation algorithm achieves
this in O(log2 n) steps.
Since there are only q k vectors in Fqk , a LRS of order k is periodic:
there exist integers n0 and r such that sn+r = sn , ∀n ≥ n0 . The
smallest such n0 is called the least preperiod and the smallest such r
is the least period of (sn ). The least period of a LRS of order k is at
most q k − 1. For cryptographic applications, one is interested in LRS
with preperiod 0 and least period as large as possible, i.e. q k − 1. In
order to determine the least period and the least preperiod of a LRS
(sn ) satisfying (*), define a characteristic polynomial f of (sn ) as the
characteristic polynomial of A:

f = X k − a0 − a1 X − ... − ak−1 X k−1 ∈ Fq [X].

Let FqN be the Fq -vector space of all sequences of elements of Fq

and let T : FqN → FqN be the left shift operator, T ((x0 , ..., xn , ...)) =
(x1 , ..., xn+1 , ...). It follows that f (T )((sn )) = (0), the zero sequence.
The monic polynomial m ∈ Fq [X] which is the generator of the ideal

{h ∈ Fq [X]|h(T )((sn )) = (0)}

is called the minimal polynomial of (sn ). Thus, m divides any char-

acteristic polynomial f . The minimal polynomial carries the relevant
information on the periodicity of (sn ):
4.1 Theorem. [13] Let (sn ) be a LRS and let m ∈ Fq [X] be its
minimal polynomial. Then the least period of (sn ) is the order of m
and the least preperiod of (sn ) is the multiplicity of 0 as a root of m.
The order ord(g) of a nonzero polynomial g ∈ Fq [X] is defined as
the least positive integer e for which g divides (X e − 1)X k for some
k ≥ 0. This notion is connected to the primitive polynomials: The
polynomial g ∈ Fq [X] of degree n is primitive if and only if g(0) 6= 0
and the order of g is q n − 1 ([12], Theorem 3.16).

163
 E. Cortellini

A LRS (sn ) of order k whose minimal polynomial m is primitive is

called a maximal period sequence. If deg(m) = k, then the least period
of such a sequence is q k − 1 by the theorem above. Thus the collection
of the state vectors {si |i = 0, ..., q k−2 } equals all nonzero vectors in Fqk .
This property of maximal period sequences makes them attractive for
many applications.
In order to give the analogue of the DLP in the more general setting
of linear recurring sequences, the following notion is needed: for a LRS
σ = (sn ) and a positive integer d, the decimation of index d of σ is
σ (d) = (snd ) (i.e, the sequence obtained by taking every d-th term of σ).
The decimated sequence σ (d) is again a LRS and in fact a characteristic
polynomial fd is obtained from a characteristic polynomial f of σ as
follows: if α1 , ..., αk are the roots of f in its splitting field over Fq , then
fd is the polynomial in Fq [X] with roots α1d , ..., αkd . This follows from
the fact that a chracteristic matrix for σ (d) is Ad (see [22]).
The analogue to the DLP becomes the following: given the charac-
teristic polynomial f of a LRS σ and the characteristic polynomial fd
of the decimated sequence σ d , find the decimation index d. Niederreiter
[23] has introduced a family of cryptosystems based on these principles.

References
[1] L. M. Adleman, A subexponential algorithm for the discrete loga-
rithm problem with applications to cryptography, Proc. 20th IEEE
Found. Comp. Sci. Symp., pp. 55–60, 1979.

[2] E. Bach, Discrete logarithms and factoring, Computer Science Di-

vision (EECS), University of California, UCB/CSD 84/186, 1984.

[3] R.P. Brent, An improved Monte Carlo factorization algorithm,

BIT 20, pp. 176–184, 1980.

[4] J. Buchmann, M.J Jacobson, E. Teske, On some computational

pro-blems in finite abelian groups, Math. of Computation, 66: pp.
1663–1687, 1997.

164
 Finite fields and cryptology

[5] J. Buchmann and H.C. Williams, A key exchange system based on

imaginary quadratic fields, J. Cryptology 1, pp. 107–118 (1988).
[6] D. Coppersmith, Evaluating logarithms in GF(2n ), in Proc. 16th
ACM Symp. Theory of Computing, pp. 201–207, 1984.
[7] D. Coppersmith, Fast evaluation of logarithms in fields of charac-
teristic two, IEEE Trans. Inform. Theory IT-30, pp. 587–594, 1984.
[8] W. Diffie and M.E. Hellman, New directions in cryptography, IEEE
Transactions on Information Theory, IT-22: pp. 644–654, 1976.
[9] T. ElGamal, A public key cryptosystem and a signature scheme
based on discrete logarithms, IEEE Trans. Inform. Theory 31, pp.
469–472 (1985).
[10] N. Koblitz, A Course in Number Theory and Cryptography,
Springer 1987.
[11] A. G. Konheim, Cryptography: A Primer, Wiley, 1981.
[12] R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983.
[13] R. Lidl and H. Niederreiter, Introduction to Finite Fields and their
Applications, Cambridge University Press, 1994.
[14] D. L. Long, Random equivalence of factorization and computation
of orders, Princeton University, DEECS, no. 284, 1981.
[15] U. Maurer, Towards the equivalence of breaking the Diffie-Hellman
protocol and computing discrete logarithms, in Advances in Cryp-
tology - Crypto ’94, pp. 271–281, Springer-Verlag, 1994.
[16] K.S. McCurley, The discrete logarithm problem, Cryptology and
Computational Number Theory, C. Pomerance, ed., Proc. Symp.
Applied Math. 42, pp. 49–74, AMS, Providence RI, 1990.
[17] A. Menezes, Elliptic Curve Cryptosystems, CryptoBytes (2) 1
(Summer 1995).
[18] R. Merkle, Secrecy, authentication, and public key systems, Ph.D.
dissertation, Dept. of Electrical Engineering, Stanford Univ., 1979.

165
 E. Cortellini

[19] J. C. P. Miller, On factorization, with a suggested new approach,

Math. Comp. 29, pp. 155–172, 1975.
[20] G.L. Mullen and D. White, A polynomial representation for loga-
rithms in GF(q), Acta. Arith. 47, pp. 255–271, 1986.
[21] National Institute of Standards and Technology (NIST), FIPS Pu-
blication 186: Digital Signature Standard (DSS), 1994.
[22] H. Niederreiter, A simple and general approach to the decimation
of feedback shift register sequences, Problems of Control and Infor-
mation theory 17, pp. 327–331, 1988.
[23] H. Niederreiter, Some new cryptosystems based on feedback shift
register sequences, Math. J. Okayama Univ. 30, pp. 121–149, 1988.
[24] A.M. Odlyzko, Discrete logarithms in finite fields and their cryp-
tographic significance, Advances in Cryptology, LN in Computer
Science vol. 209, Springer Berlin, pp. 224–314, 1985.
[25] A.M. Odlyzko, Discrete logarithms: The past and the future, De-
signs, Codes, and Cryptography 19, pp. 129–145, 2000.
[26] S.C. Pohlig and M.E Hellman, An improved algorithm for com-
puting logarithms over GF(p) and its cryptographic significance,
IEEE Transactions on Information Theory, 24, pp. 106–110, 1978.
[27] J. M. Pollard, Monte Carlo methods for index computation (mod
p), Mathematics of Computation, 32(143): pp. 918–924, 1978.
[28] J. M. Pollard, Kangaroos, Monopoly and discrete logarithms, Jour-
nal of Cryptology 13, pp. 437–447, 2000.
[29] M.J.B. Robshaw and Y.L. Yin, Elliptic Curve Cryptosystems,
Technical Note, RSA Laboratories, 1997.
[30] C.P. Schnorr and H.W. Lenstra, jr., A Monte Carlo factoring al-
gorithm with linear storage, Math. of Computation, 43 (167), pp.
289–311, 1984.
[31] D. Shanks, Class number, a theory of factorization and genera, In
Proc. Symp. Pure Math. 20, pp. 415–440. AMS, Providence, R.I.,
1971.

166
 Finite fields and cryptology

[32] V. Shoup, Lower bounds for discrete logarithms and related prob-
lems, in Proc. Eurocrypt ’97, pp. 256–266, 1997.
[33] D. R. Stinson, Cryptography in theory and practice, CRC Press,
1995.
[34] D.C. Terr, A modification of Shanks’ baby-step giant-step algo-
rithm, Math. of Computation, 69: pp. 767–773, 2000.
[35] E. Teske, Square-root algorithms for the discrete logarithm problem
(a survey), Technical Report, University of Waterloo, 2001.
[36] E. Teske, Speeding up Pollard’s rho method for computing discrete
logarithms, in Algorithmic Number Theory Seminar ANTS-III,
volume 1423 of Lecture Notes in Computer Science, pp. 541–554,
Springer-Verlag, 1998.
[37] E. Teske, On random walks for Pollard’s rho method, Mathematics
of Computation, (to appear in print), 2001.
[38] E. Teske, Computing discrete logarithms with the parallelized kan-
garoo method, Research Report CORR 01-01, Department of Com-
binatorics and Optimization, University of Waterloo, Waterloo,
Ontario, Canada, 2001. 18 pages.
[39] P. K. S. Wah and M. Z. Wang, Realization and application of the
Massey-Omura lock, pp. 175–182, in Proc. Intern. Zurich Seminar,
March 6–8, 1984.
[40] A. E. Western and J. C. P. Miller, Tables of Indices and Primi-
tive Roots, Royal Society Mathematical Tables, vol. 9, Cambridge
Univ. Press, 1968.
Ennio Cortellini, Received May 6, 2003

MET Department,
University of Teramo, Italy
E–mail: [email protected]

167