<<

. 16
( 18)



>>

p with a B-smooth value of p ’ 1, we see that p divides the GCD of N and
(xP (p,B) ’ 1) (mod N ) for any invertible x modulo N . Moreover, this GCD is
not N itself, except when all factors of N satisfy the p ’ 1 property. This last
case is quite unlikely. Moreover, from a practical point-of-view, it is better to
work with a sequence of exponents P (p, B ) for values of B that increase up
to B. This practical adaptation makes the exceptional bad case even rarer.
In pseudo-code, this is described as Algorithm 14.2. In the code, since p is
not known in advance, we upper bound P (p, B) by P (N, B).


Algorithm 14.2 Pollard™s p ’ 1 factoring algorithm
Require: Input composite N and smoothness bound B
Choose random element x modulo N
if GCD(x, N ) = 1 then
Print ˜GCD(x, N ) is a factor™ and Exit
end if
for All primes q from 2 to B do
log(N )
Let Q ←’ q log(q)
Let x ←’ xQ mod N
if GCD(x ’ 1, N ) = 1 then
Print ˜GCD(x ’ 1, N ) is a factor™ and Exit
end if
end for
Print ˜No factor found™




14.3.2 Elliptic curve factoring
To generalize Pollard™s p ’ 1 to elliptic curves, it is useful to study the
behavior of the group law of an elliptic curve E when considered modulo a
composite integer N . Assume that we are given points modulo N on the ellip-
tic curve and that we try to apply the usual additions formulas to these points.
We would like to look at the behavior that these formulas induced modulo




© 2009 by Taylor and Francis Group, LLC
434 Algorithmic Cryptanalysis

a factor p of N . Since the formulas for addition are algebraic expressions, it
is clear that when we apply an addition formula modulo N , we are in fact
applying the same formula modulo p. As a consequence, adding two points
modulo N usually induces an addition of the same point modulo p. Indeed, in
most cases, we need to use the same formula modulo each factor of N . How-
ever, there are some exceptional cases where the point addition would require
di¬erent formulas modulo the prime factors. Typically, if neither of the points
P and Q to be added is the point at in¬nity, this means that modulo a factor q
the two points P and Q are neither equal nor opposite and modulo another
factor p they are equal or opposite, i.e., xP = xQ (mod p). When the points
are considered modulo N , it is clear that xP = xQ (mod N ), thus we use the
formula for unrelated points and start by computing » = (yQ ’yP )/(xQ ’xP ).
However, since p divides xQ ’xP , it is not possible to invert this value modulo
N and » is not de¬ned. The good news is that when trying to compute the
inverse of xQ ’ xP modulo N using the extended Euclidean algorithm, we are
going to detect the problem and to discover the factor p of N . Similarly, when
trying to double a point P with yP = 0 (mod p), the doubling rule tries to
invert y and discovers p.
From this preliminary discussion, we see that most of the time, it is possible
to add points and double points by computing the classical addition formulas
modulo N . Moreover, when this fails, it yields a factor of N . In truth, it is
even possible to de¬ne an addition law on the curve modulo N that works in all
cases. However, this is not required for ECM since the goal is to factor N . As
a consequence, a failure of the addition formula becomes our goal. Putting the
cases of failure together, we see that addition/doubling fails when the result
is the point at in¬nity modulo some factor of N but not modulo N . Thus,
the question becomes: “How can we reach the point at in¬nity modulo some
factor p of N using point addition?”
Since an elliptic curve modulo p is a group, we know that multiplying any
point on the curve by the cardinality of the group yields the point at in¬nity.
Thus, in a nutshell the ECM algorithm works by choosing an elliptic curve
modulo N , a point P on the curve and by multiplying P by a multiple of the
cardinality of the curve when taken modulo a factor p of N . At ¬rst, this idea
may seem unworkable. A ¬rst obstruction is that given an elliptic curve E
modulo N , ¬nding a point P on E seems to be a di¬cult problem, indeed if
we ¬x the x coordinate, we need to compute the square root of x3 + ax + b,
a hard problem modulo a composite. Similarly, if we ¬x y, we need to solve
a polynomial equation of degree 3 modulo N , which we do not know how to
achieve in general. A second obstruction is that there is no known algorithm
to compute the cardinality of E modulo N or modulo a factor of N .
To remove the ¬rst obstruction, the key argument is to remark that we are
free to choose any convenient curve E. Thus, in practice, instead of choosing
E ¬rst, we may decide to ¬rst choose a point P and then to take a curve E
going through P . An even simpler alternative is to choose curves of the form
y 2 = x3 + ax + 1 and remark that the point P = (0, 1) belongs to all these




© 2009 by Taylor and Francis Group, LLC
Elliptic curves and pairings 435

curves. Moreover, since the parameter a can still be freely chosen, there are
enough possible choices of curve that remain.
The second obstruction says that we do not know how to determine a good
multiplier k to ensure that kP goes to in¬nity modulo a factor p of N . Instead,
we are going to choose multipliers that maximizes the probability of going to
in¬nity. The core remark is that when the number of points k on E modulo
p is a product of primes smaller than some bound B, then we can choose for
k as in Pollard™s p ’ 1. More precisely, we can take for k a value P (·, B), as
we did in Algorithm 14.2. The missing parameter in this expression needs to
be replaced by an upper bound on the number of points of an elliptic curve
modulo the smallest prime factor of N (see complexity analysis below).

14.3.2.1 Complexity analysis
In order to minimize the average running time of the ECM algorithm, we
assume that we are given a (tight) upper bound on p, say P . From this bound,

˜
we can derive an upper bound P = P + 2 P + 1 on the number of points of
an elliptic curve modulo p. We need to ¬nd the best value for the smoothness
bound B. The cost of the ECM is the product of two contributions, the
number of curves to try times the individual cost of each trial. On each
˜ ˜
curve, we compute a multiplication by k = P (P , B) for a cost of O(B log(P ))
arithmetic operations. Moreover, the expected number of curve to try is the
inverse of the probability that the number of points on the curve modulo p is
B-smooth.
Plugging in the smoothness probabilities given in Chapter 15 and ignoring
the logarithmic factors, we can optimize the complexity by balancing the
individual cost of each trial and the number of trials. Thus, we need to
achieve: “ ”
˜ ˜
log P log P
·log log B
B ≈ e log B .
Choosing B of the form:

˜ ˜
± log P log log P
B=e ,

we can achieve the balance when ± = 1/ 2. The expected runtime is B 2+o(1) .
˜
Moreover, we can forget the distinction between P and p without a¬ecting
the expression of the complexity. For this reason, the complexity of ECM is
usually given as: √
e 2 log p log log p ,
where p is the smallest factor of N .
The practical e¬ciency of ECM can be improved by adding a second phase
in the algorithm, often called ECM Step 2. This phase allows the algorithm to
succeed when the cardinality of the chosen curve has one prime factor larger
than the bound B, but not too large. This is discussed in details in [Mon92].




© 2009 by Taylor and Francis Group, LLC
436 Algorithmic Cryptanalysis



Exercises
1h . Implement elliptic curve operations over a small ¬nite ¬eld, say F65521 .
Do experiments with the group operation, check that it is indeed a
group, compute the order of points for several curves. Determine the
group structure of each curve. It is also interesting to consider a singular
curve, i.e., a curve with 4a3 + 27b2 = 0. Can you use the addition
formulas in this case? Try to ¬nd out whether there is a group and, if
so, what its structure is.

2. Write a program to work with small functions of the form F0 (x) +
yF1 (y) on an elliptic curve over a small ¬nite ¬eld. This should compute
the zeros of a function and be able to evaluate a function at a point.
Experiment Weil™s reciprocity with your program.

3. Assuming that a divisor (P1 )’(P2 ) is principal, show that you can write
it as:
F1 (x) + yF2 (x)
(P1 ) ’ (P2 ) = div .
G(x)
Show that this expression can be simpli¬ed until G is a polynomial of
degree at most 1. Prove that in that case, F2 = 0 and conclude.

4h . Program a simple implementation of Miller™s algorithm to compute
fP (Q) for a well-chosen elliptic curve and some well-chosen points. Try
to write explicitly fP in expanded form as F0 (x)+yF1 (x) on a computer
algebra system. For which size is this approach successful?

5. Find out how to compute the order of a point on an elliptic curve using
a birthday algorithm. Can you do it without using a large amount of
memory?

6h . Assume that you are given an elliptic curve together with a pairing
e (·, ·) from G1 — G2 to the group of -th roots of unity in a ¬nite ¬eld
Fpk . Each of the groups G1 and G2 is a subgroup of -torsion points
containing exactly element. Let Q be a point in G2 and assume that
there exists an e¬cient algorithm e’1 that given a -th root of unity ξ
outputs a point P in G1 such that e (P, Q) = ξ. Further assume that
’ 1 is a product of small primes, show that there exists an e¬cient
algorithm that makes use of e and e’1 to compute discrete logarithms
in G1 . How would you proceed for general values of ?

7. Let N = pq be an RSA number and E be an elliptic curve. Consider E
modulo N . Show using the Chinese remainder theorem that this forms
a group and determine the full structure of this group. There are some
“exceptional” points on this curve, what are they?




© 2009 by Taylor and Francis Group, LLC
Elliptic curves and pairings 437

8h . Now consider the curve E modulo p2 where p is a prime.

• Determine the structure of the curve in the general case. Show
that the exceptional points (as in the previous exercise) form a
group. Determine the order of this group. Write the group law
on the exceptional points. Can you simplify the expression of this
group law?
• In the special case where the cardinality of the curve is p, what
are the possible group structures. Given a point P , not the point
at in¬nity, on the curve modulo p, show that there are p di¬erent
points modulo p2 whose reduction modulo p is equal to P . Let P1
and P2 be two such lifts of P , what can you say about pP1 and
pP2 ?
• In the same special case, let P and Q be two points on the elliptic
curve modulo E. We would like to solve the discrete logarithm
problem Q = »P . Let P1 be a lift of P and Q1 a lift of Q, what
can you say about the relation between pP1 and pQ1 ? Under
which condition can you break the discrete logarithm problem?
• Sometimes the above condition is not satis¬ed. How can you pro-
ceed to make the method work despite that?




© 2009 by Taylor and Francis Group, LLC
Chapter 15
Index calculus algorithms




15.1 Introduction to index calculus
Index calculus is a rich area of research in number theory and cryptography.
This technique is common to a large family of algorithms that can be used for
many applications. From a number theoretic point-of-view, these algorithms
allow to factor large integers, to compute discrete logarithms in ¬nite ¬elds,
to compute the class numbers of number ¬eld and even apply to discrete
logarithms on the jacobians of some algebraic curves. From a cryptographic
perspective, the above applications are directly interesting but in addition,
index calculus techniques have recently been used to undermine the security
of several cryptographic primitives in some speci¬c contexts. With these
cryptographic primitives which, at the present time, include the plain RSA
e-th root extraction problem [JNT07] and the static Di¬e-Hellman problem,
an adversary learns enough to solve the problem on his own after asking a
large number of questions about well-chosen instances of the problem. The
total cost of index calculus in these cryptographic applications is less than
the cost of the corresponding index calculus algorithm against the underlying
number theoretic problem: factoring or computation of discrete logarithms.
To tackle this large scope, we are going to dive into index calculus algo-
rithms carefully. Indeed, some of these algorithms require much more math-
ematical machinery than others. Thus, to better focus on the key ideas, we
mostly study a typical but simple example about the computation of discrete
logarithms in ¬nite ¬elds with a well-chosen structure.
Before that, let us have a quick bird™s-eye view of the general principle of
index calculus algorithms. This principle puts two basic ideas into play. First,
in order to learn information about a mathematical structure A, we enlarge
this structure in two di¬erent but compatible ways. More precisely, we try to
construct a commutative diagram:

A
ψ2
ψ1
A1 A2 (15.1)
φ1
φ2
A


439
© 2009 by Taylor and Francis Group, LLC
440 Algorithmic Cryptanalysis

With such a diagram, any element x in A can be sent into A along two di¬erent
paths, either going through A1 or through A2 . In both cases, we reach the
same value, i.e., φ1 (ψ1 (x)) = φ2 (ψ2 (x)).
The second idea is to choose A1 and A2 in a way that allows a non-negligible
fraction of elements of either set to be written as a product of mathematical
objects belonging to reasonably small sets. The values which can be written in
this way are usually called smooth. And the sets used to write the products
are traditionally called the smoothness bases for A1 and A2 . Combining the
two ideas means that if both ψ1 (x) and ψ2 (x) can be written as products over
their respective smoothness bases, then we get an “equality” between these
two products. Note that for some index calculus algorithms, some functions
among the ψi or φi are either the identity function or some other natural map
and the above diagram can be simpli¬ed, by removing some of the arrows or
sets that are involved.
In this setting, index calculus algorithms create and collect many “equal-
ities.” Once these equalities are constructed, they need to be combined in
speci¬c ways, in order to solve the problem at hand. The way of combining
the equalities greatly vary from one problem to the next, as we show in the
sequel. However, linear algebra always plays a role in this process.
In addition to the basic structure described above, index calculus algorithms
also have their asymptotic complexities in common. Indeed, they all have
complexities expressed as


1’±
LN (±, c) = exp (c + o(1)) log(N )± log log(N ) , (15.2)


where N is the number that characterizes the problem being considered and
where 0 < ± < 1 and c > 0 are two constants. The notation LN (±) is
frequently used as a shorthand when c is left unspeci¬ed. Moreover, when N is
clear from the context, we simply write L(±). These strange looking functions
arise from the probability for values to be smooth. Two values of ± are widely
encountered in index calculus algorithms, they usually have complexity either
L(1/2) of L(1/3). The reader should be aware that a change from ± = 1/2 to
± = 1/3 means much more in terms of complexity than a similar change for the
value of the second parameter c. Indeed, complexity of the type L(±) becomes
polynomial in log(N ) when ± tends to zero and exponential in log(N ) when ±
tends to one. Between these two extreme values of ±, the complexity is called
subexponential. Thus, ± controls the change from polynomial to exponential,
and it clearly has much more impact than c which, in the polynomial case,
merely controls the degree of polynomial. Note that log(N ) is the bitsize of
the value N which characterizes the problem and thus the relevant parameter
to use to de¬ne polynomial or exponential complexity.




© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 441




15.2 A simple ¬nite ¬eld example
15.2.1 Overview
To describe in details the principle of index calculus, without having to
tackle too many mathematical obstructions, we start by considering the prob-
lem of computing discrete logarithms in a ¬nite ¬eld Fpn , where the relative
values of p and n are chosen to make things as simple as possible. More
precisely, we let Q denote pn and consider the case where:

p = LQ (1/3, θ) and (15.3)
2/3
log(Q) 1 log(Q)

n= ,
log(p) θ log log(Q)


where θ is a constant to be determined later on. We let d = n and choose
two polynomials of degree d: f1 and f2 . These two polynomials are used to
implicitly de¬ne the ¬nite ¬eld FQ . The idea is to ¬x two polynomial relations
modulo p between two variables x and y:

y = f1 (x) and x = f2 (y). (15.4)

For these two relations to hold, we need to have x = f2 (f1 x)). Thus, x needs
to be a root of f2 (f1 (x)) ’ x. Assume that this polynomial, whose degree is
d2 ≥ n has an irreducible factor of degree n and denote this factor by Ix . Then
Ix can be used to de¬ne the ¬nite ¬eld FQ . Let ± denote the image of x in the
¬nite ¬eld using the canonical projection, i.e., ± is the class of the polynomial
x modulo Ix (and of course modulo p). Let β = f1 (±), then in the ¬nite ¬eld,
we also have ± = f2 (β). Indeed, by construction, f2 (β) = f2 (f1 (±)) is equal
to ± plus a multiple of Ix (±). And, by de¬nition of the ¬nite ¬eld, Ix (±) = 0
in FQ .
The element β of the ¬nite ¬eld has a characteristic polynomial Iy of degree
n. Indeed, the degree is at most n, since β belongs to Fpn , and if the degree is
less than n, then β belongs to a proper sub¬eld and so does ± = f2 (β). Since
by de¬nition ± generates FQ , this is not possible. Thanks to the relation
β = f1 (f2 (β)), we see that Iy is a divisor of degree n of the polynomial
f1 (f2 (y)) ’ y modulo p.
As a consequence of the existence of Ix and Iy , we have two di¬erent rep-
resentations of the ¬nite ¬eld FQ , one with generator ± and the other with
generator β, together with explicit low degree isomorphisms between the two
representations, given by β = f1 (±) and ± = f2 (β). Putting these two repre-




© 2009 by Taylor and Francis Group, LLC
442 Algorithmic Cryptanalysis

sentations together, we obtain the following commutative diagram:

Fp [x, y]
x’f2 (y)
y’f1 (x)
(15.5)
Fp [x] Fp [y]
x’±
y’β
FQ

Using this commutative diagram, we now take polynomials of the form
xy + ax + by + c for arbitrary values of a, b and c in Fp . Each polynomial
of this form is transformed into a univariate polynomial in x of degree d + 1
when we substitute f1 (x) for y and into a univariate polynomial in y of degree
d + 1 when we substitute f2 (y) for x. Thus, we obtain the following equality
in the ¬nite ¬eld Fq :

±f1 (±) + a± + bf1 (±) + c = βf2 (β) + af2 (β) + bβ + c. (15.6)

We only keep a fraction of these equalities. More precisely, we focus on the
equations where both sides factor into linear polynomials. To obtain these
equations, at least three di¬erent approaches can be considered. The ¬rst
method is to simply factor L(x) = xf1 (x) + ax + bf1 (x) + c and R(y) =
yf2 (y) + af2 (y) + by + c and to check that both only contain factors of degree
1. Recalling the algorithm for factoring polynomials over a ¬nite, this can be
slightly improved by checking that xp ≡ x (mod L(x)R(x)), in Fp [x]. The
second method is to use a sieving algorithm as in Chapter 4. The third
method is to use Bernstein™s algorithm for avoiding sieving, also presented in
Chapter 4. For implementations of the methods, please refer to the book™s
website.
Each equation left after selection can be rewritten as a multiplicative equal-
ity between d+1 linear polynomials ±’u for constants u in Fp and d+1 linear
polynomials β ’ v for constants v in Fp . Given any multiplicative generator γ
of FQ , the multiplicative equalities can be transformed into additive relations
between the logarithms in base γ. As a consequence, each equation becomes:
d+1 d+1
logγ (± ’ ui ) ≡ logγ (β ’ vi ) (mod Q ’ 1), (15.7)
i=1 i=1

where the modulus is the order of γ. Clearly, the total number of unknowns,
i.e., of discrete logarithm values, to determine is 2p. Thus, given 2p equa-
tions, we hope to be able to obtain the logarithm values. However, there is
a simple obstruction that prevents this method from working directly. This
obstruction stems from the fact that our system of equation possesses a par-
asitical solution. Indeed, each equation has d + 1 unknowns on each side.
As a consequence, setting every unknown to 1 gives a solution to the system
of equations. To remove this parasitical solution, it su¬ces to ¬nd a single
equation of a di¬erent type. This can be done by considering the polynomial




© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 443

x + a for a value of a such that f2 (y) + a splits into linear factors. This yields
an equation with a single unknown on the left-hand side and d unknowns on
the right-hand side. Once this is done, there are no more evident parasitical
solutions. Moreover, in practice, with a few extra equations thrown in as a
precaution, the system of equations has a kernel of dimension 1. As a con-
sequence, up to an arbitrary multiplicative factor, the system has a unique
solution. In fact, to each di¬erent choice of the logarithm™s base γ corresponds
a di¬erent choice of a multiplicative constant. Note that trying to solve the
linear system modulo Q ’ 1 is often a bad idea. The problem is that Q ’ 1
may contain small factors, which can lead to trouble when the linear algebra
is done using an iterative algorithm. Instead, we should, if possible, factor
Q ’ 1 and work modulo each factor, solving the above system for large factors
and using a baby step, giant step or another birthday paradox based algo-
rithm for the small factors. Note that we already know that p ’ 1 is a factor
of Q ’ 1. When Q ’ 1 is hard to factor, we can still obtain the logarithm
by using an iterative algorithm to solve the linear system modulo composite
factors of Q ’ 1 after eliminating the small factors of Q ’ 1.

15.2.1.1 Individual logarithms
After solving the linear system, we obtain the discrete logarithms of all the
values ± ’ u or β ’ v in the ¬nite ¬eld. However, the work is not complete.
Indeed, we would like to be able to compute the discrete logarithms of arbi-
trary values in FQ . The key to this is to use a descent algorithm, where the
discrete logarithm of an arbitrary polynomial is expressed in terms of discrete
logarithms of polynomials with smaller degrees. This idea is used iteratively,
until we reach the point where everything is expressed as a function of discrete
logarithms of linear polynomials, which are already known. To express the
logarithm of a polynomial q(x) of degree dq on the left-hand side in terms
of polynomials of lower degree, we consider bivariate polynomials T (x, y) of
degree t, separately in each variable, such that q(x) divides the left-hand side
projection T (x, f1 (x)). Constructing these polynomials can be done using
linear algebra modulo p. More precisely, we build a matrix whose columns
are indexed by monomial xdx y dy with 0 ¤ dx ¤ t and 0 ¤ dy ¤ t. Each
of the (t + 1)2 columns gives the representation of the projection xdx f1 (x)dy
(mod q(x)) of the corresponding monomial. In the ¬rst row, we ¬nd the con-
stant coe¬cients of these polynomials, in the second row the x coe¬cient and
so on. Since q(x) has degree dq , there are dq rows in the matrix. Now, an
element of the kernel of the matrix can be interpreted as a polynomial in x
and y whose projection is equal to 0 modulo q. Reciprocally, each polyno-
mial T (x, y) of degree at most t in x and y, whose projection is a multiple of
q, belongs to the kernel of the matrix. As a consequence, to enumerate the
polynomials T (x, y) it su¬ces to compute a basis of the kernel and to look at
all the possible linear combinations of the kernel elements.
Polynomials q(y) on the right-hand side are treated in the same way, re-




© 2009 by Taylor and Francis Group, LLC
444 Algorithmic Cryptanalysis

versing the roles of x and y. Note that during the descent algorithm, we
alternatively encounter both cases.
At each step, we ¬nd a relation between a polynomial q and several poly-
nomials of lower degree. As a consequence, the descent produces a tree of
computation. The root of the tree is the original values whose discrete loga-
rithm is desired. The leaf of the tree are the linear polynomials. To make sure
that the descent is feasible, we need to ensure that each step of the descent
can be performed quickly enough and that the tree of descent has a reasonable
number of nodes. To satisfy this condition, we need to carefully balance the
speed of the descent. If we try to descend too quickly, then each individual
step is too costly. If we descend too slowing, the size of the tree becomes too
large and the complete computation cannot be done. The complexity analysis
below shows how to balance the speed of the descent adequately.

15.2.1.2 Complexity analysis
To perform the complexity analysis, we need to know the probability for a
polynomial of degree ∆ to split into irreducible factors of degree δ. In fact,
in the early steps of the computation, we only need the case where δ = 1.
With this case, the analysis is quite simple, the total number of (monic)
polynomials of degree ∆ is p∆ , while the number of polynomials that split is
approximately p∆ /∆!. Thus, the probability that a given polynomial splits is
1/∆!. For the analysis, it is convenient to write that the logarithm in base p
of the probability is close to ’∆ logp (∆). We discuss smoothness probabilities
in more details in Section 15.5.
For arbitrary δ, the result generalizes into the following theorem from
[PGF98].


THEOREM 15.1
Let P be a random polynomial of degree ∆ over a ¬nite ¬eld Fp . Let pr(∆, δ)
be the probability that P factors into a product of irreducible polynomials of
degree at most δ.
Then:
’ logp (pr(∆, δ)) ≈ ’(∆/δ) logp (∆/δ)

For completeness, we prove the lower bound part of this theorem in Sec-
tion 15.5. Indeed, such a lower bound su¬ces for the complexity analysis.
In our analysis, as in many index calculus algorithms, we make an essential
heuristic hypothesis. When we generate the equations, we simultaneously
consider two related polynomials L(x) = xf1 (x) + ax + bf1 (x) + c and R(y) =
yf2 (y) + af2 (y) + by + c, and ask for both to be smooth. When the two
polynomials are related in this fashion, it is not known how to analyze the
probability for both to factor in the right way. Instead, we make the heuristic
assumption that L(x) and R(y) behave as random independent polynomials
in this respect. We need a similar hypothesis during the descent phase.




© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 445

With this hypothesis, the probability that both L(x) and R(y) split is ((d +
1)!)’2 since both have degree d + 1. Taking the logarithm, we ¬nd 2(d +
1) log(d + 1). Another way to state the heuristic is to say that L(x)R(x)
behaves as a random polynomial with respect to the splitting property. This
yields a probability 1/(2d + 2)! and taking logarithm we ¬nd 2(d + 1) log(2(d +
1)). We can check asymptotically that both expressions are equivalent and
can be written as 2d log(d)(1 + o(1)).

Complexity of ¬nding and solving the linear system of equations.
Here, there are two important parameters to take into account:
1/3
1 log(Q)
p = LQ (1/3, θ) and d = √ · . (15.8)
log log(Q)
θ
We have a total of 2p unknowns and thus need to generate a little more than
2p equations. The linear algebra step essentially costs (2p)2 operations. While
generating the equations, we have three degrees of freedom a, b and c. Each
triple (a, b, c) yields an equation with probability (1/d!)2 . We can hope to
generate enough equations when:

p3 p2
≥ d!2 .
≥ 2p or (15.9)
d!2 2
Note that when d!2 is close to the upper bound p2 /2 the generation of the
equations step costs roughly p3 operations, while the linear algebra costs 4p2 .
In the opposite direction, when d!2 < p the linear algebra step costs more than
the generation of the equations. The two steps are balanced when 4p ≈ d!2 .
Let us analyze this middle case. Taking the logarithm of the condition we
¬nd:

log(p) ≈ 2d log(d) i.e.
2
θ log(Q)1/3 log log(Q)2/3 ≈ √ log(Q)1/3 log log Q2/3 , (15.10)

since log(d) ≈ log(Q)/3. Thus, the balance condition becomes:
2
2 2 3
3
θ = √ or θ = = 4/9. (15.11)
3

Since in this middle case the complexity of generating and solving the system
of equations is approximately p2 , it can be written as:
3
LQ (1/3, 2θ) = LQ 1/3, 32/9 .

When p is larger than this value, the complexity is dominated by the linear
algebra and as a result costs more than in the balance case. When p is smaller




© 2009 by Taylor and Francis Group, LLC
446 Algorithmic Cryptanalysis

and still conforms to Equation (15.9), the complexity slowly decreases, at the
limit, we ¬nd p2 /2 = d!2 which corresponds to:
2
2 1 3
3
2θ = √ or θ = = 1/9. (15.12)
3

In this case, the complexity is dominated by the generation of the equa-
tions which needs to consider p3 candidate triples. Thus, the total cost is
LQ (1/3, 3/91/3 ) = LQ (1/3, 31/3 ).

Complexity of individual discrete logarithms To determine the com-
plexity of the individual discrete logarithms, we need a detailed analysis of
the descent parameters. Assume that we are given a polynomial1 q(x). At
most the degree dq of q is n ’ 1 since q represents an element of the ¬nite ¬eld.
We use a descent step to express q in terms of polynomials of smaller degree.
Remember that this is done by searching for a bivariate polynomial T (x, y) of
degree t, in each variable, such that q(x)|T (x, f1 (x)). Without the divisibility
condition, there are (t + 1)2 ’ 1 degrees of freedom that determine2 T . The
divisibility condition adds dq linear constraints. Thus, the total number of
polynomials we can consider is:
2
’dq ’1
NT = p(t+1) . (15.13)

We want both T (x, f1 (x)) and T (f2 (y), y) to split into small enough fac-
tors. These two polynomials have degree td, their probability to simultane-
ously split into factors of degree t has a logarithm approximately equal to
’2(td/t ) log(td/t ). For the descent to be e¬ective, each step should not cost
too much. It is tempting to try making the probability comparable to the
probability encountered while generating the main set of equations. Making
this choice, we now need to make sure that we can really ¬nd an equation
during this step of the descent. This means that we need to check that the
number of polynomials NT is larger than the inverse of the probability, i.e.:
2
(t + 1)2 ’ dq ’ 1 ≥ 2(td/t ) logp (td/t ) = 2d logp (d) ≈ . (15.14)
3θ3/2
Thus, t + 1 can be chosen as the integer obtained by rounding up the square
root of dq plus some constant µ = 1 + 3θ2 . Clearly, with this choice of pa-
3/2

rameters for the descent, each individual step does not cost too much, since its
cost is comparable to the cost of computing a single equation during the initial
construction of the system of equation. Moreover, the tree of descent has a
(i)
small height. Indeed, we start from d1 = n and at step i we go down from dq
q


1 Orq(y), both cases are completely symmetric.
2 We subtract 1 from (t + 1)2 because multiplying T by a constant does not change the
degrees of its factors. This remark removes one degree of freedom.




© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 447

(i ) (i)
to dq 1 = dq + µ . This means that log(dq ) roughly follows a geometric
progression of ratio 1/2 and that we have a height bounded by O(log log(n)).
As a consequence, the descent tree contains a polynomial number of nodes
and does not impact the constants in the subexponential complexity.
Since θ ≥ 3’1/3 according to Section 15.2.1.2, we have µ < 1.39, and the
above analysis allows us to descent until we reach dq = 2. Indeed, for dq = 3

we choose t + 1 = 3 + µ = 3 or t = 2 and we split the polynomials into
factors of degree 2. Since our factor basis only contains polynomials of degree
1, we need to analyze separately an extra step to descent from degree 2 to
degree 1. In this ¬nal step of descent, we have dq = 2. The ¬rst option
is to consider polynomials T (x, y) = xy + ax + by + c for triples (a, b, c) of
coe¬cients in Fp . Since we have two linear conditions to make sure that
the degree 2 polynomial divides either T (x, f1 (x)) or T (f2 (y), y), there are p
possible choices for T . After substitution, the degree on each side is d + 1 and
it can be reduced to d ’ 1 on one side by removing the known factor of degree
2. The probability of having two polynomials that split into degree one is:
1
.
(d ’ 1)!(d + 1)!
2
Asymptotically, this is LQ (1/3, ’ 3√θ ). We can hope to ¬nd a relation if this
probability is at least 1/p, i.e., when θ ≥ (2/3)2/3 . This corresponds either to
the balanced case of Section 15.2.1.2 or to large prime p.
When p is a smaller prime, we need to consider a second option and to
look at unbalanced polynomials3 , T (x, y) = x2 y + axy + bx2 + cx + dy + e.
Removing the degrees of freedom due to the two linear conditions, we are left
with p3 possible polynomials. The probability of splitting correctly is:
1
.
(2d ’ 1)!(d + 1)!
1
Asymptotically, this is LQ (1/3, ’ √θ ). In this case, there is enough freedom to
¬nd a relation if this probability is at least 1/p3 , i.e., when θ ≥ (1/3)2/3 . As a
consequence, we can asymptotically address all the cases of Section 15.2.1.2.
However, the reader should note that for practical computations, this option
of a smaller prime should be handled with care. The di¬culty stems from the
fact that for moderate values of d, such as, for example, d = 7, there is a
considerable gap between d!2 and (2d)!. Thus for some practical choices of
parameters, we may encounter discrete logarithm computations where the
initial system of linear equations can be constructed and solved reasonably
quickly, while the ¬nal step of the descent from degree 2 to degree 1 remains
unpractical. For example, when choosing p = 65537 and n = 49, i.e., d = 7

3 Weassume here that the degree 2 polynomial we are trying to express is on the x side.
Otherwise, we need to reverse the roles of x an y.




© 2009 by Taylor and Francis Group, LLC
448 Algorithmic Cryptanalysis

we run into this exact problem. It is possible to perform the early steps
reasonably easily on today™s computers and obtain the discrete logarithms of
basis elements; moreover, the early steps of the descent down to polynomials
of degree 2 do not present any special di¬culty. However, the last descent step
from polynomials of degree 2 to linear polynomials does not work, because we
do not have enough degrees of freedom and we cannot conclude the discrete
logarithms computation.


15.2.2 A toy example
In this section, we illustrate the above method by computing discrete log-
arithm in F1014 . Let us de¬ne p = 101 and n = 4 together with the two
polynomials:
f1 (x) = x2 + 1 and f2 (y) = y 2 + 2. (15.15)
Then the polynomial f2 (f1 (x)) ’ x = x4 + 2x2 ’ x + 3 is irreducible modulo
p and so is the polynomial f1 (f2 (y)) ’ y = y 4 + 4y 2 ’ y + 5. Thus, the two
relations y = f1 (x) and x = f2 (y) implicitly de¬ne the ¬nite ¬eld F1014 .
With this de¬nition for f1 and f2 , we now search for smooth multiplica-
tive relations involving the two ¬nite ¬eld representation. Before considering
polynomials of the form xy + ax + by + c, we ¬rst look at polynomials x + a,
y + a and x + ay + b. The advantage of these polynomials is that, since they
give relations between polynomials in x and y of lower degree, we expect a
better probability of smoothness. In addition, having equations of this type
in our system removes the all ˜1™ parasitical solution from the linear system
we are constructing.
In our example, we obtain 51 equations using polynomials of the form x + a
and also 51 equations from polynomials y + a. This can be easily interpreted
by remarking that x + a is always expressed as a linear term on the x side
and that on the y side we are looking at the factorization of y 2 + 2 + a. This
polynomial splits into linear factors if and only if ’(a + 2) is either 0 or a
quadratic residue. Since in F101 there are 50 quadratic residues and 50. In
addition, we only need another hundred equations and they are obtained by
considering polynomials x + ay + b with a = 0. In fact, it su¬ces to consider
values of a in [1 · · · 5] and test all values of b to obtain enough equations.
Typical equations are:

x + 7 = (y + 30) · (y + 71) (mod 101), (15.16)
(x + 44) · (x + 57) = y + 83 (mod 101),
(x + 6) · (x + 96) = (y + 49) · (y + 53) (mod 101) [from x + y + 70],
3(x + 64) · (x + 71) = (y + 4) · (y + 100) (mod 101) [from x + 3y + 95].

It is interesting to remark that the fourth among Equations (15.16) involves
a ¬nite ¬eld constant 3 in addition to the linear polynomials x + u or y + v.
Clearly, in general, we may expect arbitrary constants to appear, since from




© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 449

x + ay + b we generate an equation which has a as coe¬cient of the highest
degree monomial on the x side. A natural question to consider is the impact of
these constants on the discrete logarithm computations. Indeed, when writing
the linear equations we get as additional unknowns the logarithms of the p ’ 1
non-zero constants. At ¬rst, this seems to imply that we need to collect 3p
equations instead of 2p. However, there are simple ways of sidestepping this
issue. One possible idea is to simply avoid equations from polynomials of the
form x + ay + b since these equations are the only ones that involve constants.
In fact, this is not a good idea, because these polynomials have a better chance
of yielding equations than the more general form xy + ax + by + c, thus using
them speeds up the computations.
To get rid of the extra p unknowns coming from the constants, it is better to
remark that since F— is a multiplicative subgroup of F—n , its order p’1 divides
p p
n
the order p ’1 of the full group. Thus, thanks to the Pohlig-Hellman method,
see Section 6.4.1, we are going to deal separately with the discrete logarithms
modulo p ’ 1 and modulo q = (pn ’ 1)/(p ’ 1). Since p ’ 1 is small, we can use
Pollard™s rho algorithm to determine this part of the discrete logarithm and
thus we do not require any equation at all modulo p ’ 1. Thus, we are only
looking at our equations modulo q. At that point, we should remember that
to focus on the discrete logarithm modulo q using Pohlig-Hellman method,
we need to raise everything to the power p ’ 1 in order to get rid of this
factor. This means that in our equations, we do not need the logarithms of
the constants in F— but the logarithms of the non-zero constants raised to the
p
power p ’ 1. Of course, thanks to Fermat™s little theorem, all these powers
are equal to 1. As a consequence, since the logarithm of 1 is zero, we can
completely forget the constants when setting up the linear system for discrete
logarithm modulo q.
The equations we need are summarized in three tables. Table 15.1 describes
all equations coming from x + a, Table 15.2 describes all equations coming
from y + a and Table 15.3 contains enough equations of the form x + ay + b
to get a complete system.




15.3 Generalization to ¬nite ¬elds with small enough
characteristic
The method described in Section 15.2 can in fact be generalized to all values
of the characteristic smaller than L(1/3). More precisely, discrete logarithms
in ¬nite ¬elds FQ = Fpn , with p smaller than LQ 1/3, 3’1/3 can be com-
puted using such a generalization. In the range of p from LQ (1/3, 3’1/3 ) to
LQ (1/3, ˜), for some value of ˜ we can use the algorithm of Section 15.2 itself.
Beyond that point, we need a variation of the number ¬eld sieve described




© 2009 by Taylor and Francis Group, LLC
450 Algorithmic Cryptanalysis




(2, 81, 20) (3, 55, 46) (4, 87, 14) (7, 30, 71) (11, 54, 47)
(12, 17, 84) (14, 40, 61) (15, 65, 36) (17, 48, 53) (18, 9, 92)
(19, 22, 79) (20, 33, 68) (21, 52, 49) (22, 73, 28) (23, 51, 50)
(28, 77, 24) (29, 26, 75) (31, 13, 88) (34, 41, 60) (35, 8, 93)
(41, 19, 82) (43, 64, 37) (45, 85, 16) (47, 31, 70) (50, 7, 94)
(52, 59, 42) (54, 67, 34) (56, 89, 12) (62, 21, 80) (63, 95, 6)
(66, 29, 72) (68, 58, 43) (69, 63, 38) (74, 96, 5) (75, 78, 23)
(76, 86, 15) (77, 74, 27) (78, 83, 18) (79, 11, 90) (80, 25, 76)
(82, 57, 44) (83, 4, 97) (85, 69, 32) (86, 66, 35) (90, 3, 98)
(93, 62, 39) (94, 45, 56) (95, 99, 2) (98, 100, 1) (99, 0, 0)
(100, 91, 10)


Table 15.1: Equations (x + u) = (y + v1 ) · (y + v2 ) as triples (u, v1 , v2 )




(91, 10, 0) (81, 20, 3) (55, 46, 4) (14, 87, 5) (30, 71, 8)
(54, 47, 12) (84, 17, 13) (61, 40, 15) (36, 65, 16) (53, 48, 18)
(9, 92, 19) (22, 79, 20) (68, 33, 21) (49, 52, 22) (73, 28, 23)
(50, 51, 24) (24, 77, 29) (75, 26, 30) (13, 88, 32) (41, 60, 35)
(93, 8, 36) (19, 82, 42) (64, 37, 44) (85, 16, 46) (70, 31, 48)
(94, 7, 51) (59, 42, 53) (34, 67, 55) (89, 12, 57) (80, 21, 63)
(6, 95, 64) (29, 72, 67) (43, 58, 69) (63, 38, 70) (5, 96, 75)
(23, 78, 76) (15, 86, 77) (74, 27, 78) (83, 18, 79) (90, 11, 80)
(76, 25, 81) (44, 57, 83) (4, 97, 84) (32, 69, 86) (66, 35, 87)
(3, 98, 91) (62, 39, 94) (45, 56, 95) (99, 2, 96) (100, 1, 99)
(0, 0, 100)


Table 15.2: Equations (x + u1 ) · (x + u2 ) = (y + v) as triples (u1 , u2 , v)




© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 451




(1, 4) (27, 75, 25, 77) (1, 10) (10, 92, 43, 59) (1, 38) (30, 72, 45, 57)
(1, 44) (94, 8, 89, 13) (1, 50) (56, 46, 74, 28) (1, 51) (28, 74, 66, 36)
(1, 52) (36, 66, 78, 24) (1, 53) (78, 24, 33, 69) (1, 54) (33, 69, 62, 40)
(1, 55) (40, 62, 26, 76) (1, 58) (95, 7, 55, 47) (1, 61) (19, 83, 16, 86)
(1, 69) (12, 90, 96, 6) (1, 70) (6, 96, 49, 53) (1, 74) (52, 50, 51, 51)
(1, 75) (51, 51, 61, 41) (1, 79) (31, 71, 5, 97) (1, 80) (5, 97, 65, 37)
(1, 88) (98, 4, 34, 68) (1, 91) (11, 91, 15, 87) (1, 94) (99, 3, 42, 60)
(1, 95) (42, 60, 73, 29) (1, 96) (29, 73, 84, 18) (1, 97) (18, 84, 2, 100)
(1, 98) (100, 2, 23, 79) (1, 99) (23, 79, 0, 1) (2, 4) (72, 80, 47, 56)
(2, 8) (44, 7, 72, 31) (2, 18) (73, 79, 54, 49) (2, 21) (57, 95, 34, 69)
(2, 24) (37, 14, 52, 51) (2, 29) (60, 92, 78, 25) (2, 36) (76, 76, 9, 94)
(2, 44) (96, 56, 65, 38) (2, 46) (21, 30, 17, 86) (2, 48) (62, 90, 71, 32)
(2, 51) (88, 64, 95, 8) (2, 63) (97, 55, 22, 81) (2, 64) (59, 93, 96, 7)
(2, 70) (11, 40, 64, 39) (2, 75) (33, 18, 97, 6) (2, 76) (85, 67, 79, 24)
(2, 77) (13, 38, 87, 16) (2, 78) (98, 54, 28, 75) (2, 80) (43, 8, 12, 91)
(2, 84) (3, 48, 5, 98) (2, 86) (26, 25, 70, 33) (2, 87) (71, 81, 36, 67)
(2, 91) (61, 91, 99, 4) (2, 95) (58, 94, 57, 46) (2, 96) (100, 52, 3, 100)
(2, 99) (0, 51, 0, 2) (3, 5) (61, 74, 76, 28) (3, 6) (82, 53, 26, 78)
(3, 8) (21, 13, 39, 65) (3, 12) (70, 65, 60, 44) (3, 18) (96, 39, 71, 33)
(3, 22) (84, 51, 36, 68) (3, 24) (69, 66, 83, 21) (3, 27) (45, 90, 45, 59)
(3, 29) (20, 14, 94, 10) (3, 45) (41, 94, 95, 9) (3, 46) (38, 97, 90, 14)
(3, 53) (16, 18, 37, 67) (3, 54) (30, 4, 25, 79) (3, 56) (17, 17, 63, 41)
(3, 59) (27, 7, 96, 8) (3, 63) (58, 77, 87, 17) (3, 67) (55, 80, 49, 55)
(3, 71) (63, 72, 97, 7) (3, 82) (22, 12, 66, 38) (3, 85) (95, 40, 82, 22)
(3, 90) (54, 81, 69, 35) (3, 95) (64, 71, 100, 4) (3, 96) (33, 1, 61, 43)
(3, 97) (28, 6, 74, 30) (3, 98) (0, 34, 85, 19) (3, 100) (93, 42, 80, 24)
(4, 1) (22, 54, 1, 3) (4, 2) (71, 5, 2, 2) (4, 6) (87, 90, 22, 83)
(4, 11) (39, 37, 73, 32) (4, 15) (38, 38, 49, 56) (4, 16) (43, 33, 19, 86)
(4, 19) (48, 28, 38, 67) (4, 21) (45, 31, 50, 55) (4, 24) (23, 53, 35, 70)
(4, 32) (56, 20, 26, 79) (4, 35) (84, 93, 15, 90) (4, 38) (12, 64, 43, 62)
(4, 39) (52, 24, 10, 95) (4, 45) (26, 50, 21, 84) (4, 51) (68, 8, 72, 33)
(4, 58) (79, 98, 69, 36) (4, 60) (6, 70, 91, 14) (4, 67) (85, 92, 97, 8)
(4, 73) (32, 44, 65, 40) (4, 79) (99, 78, 80, 25) (4, 80) (41, 35, 17, 88)
(4, 83) (74, 2, 92, 13) (4, 86) (19, 57, 59, 46) (4, 94) (75, 1, 5, 100)
(4, 97) (0, 76, 64, 41) (4, 99) (60, 16, 4, 0) (5, 3) (9, 72, 25, 81)
(5, 4) (39, 42, 2, 3) (5, 9) (63, 18, 77, 29) (5, 10) (71, 10, 79, 27)
(5, 12) (85, 97, 66, 40) (5, 15) (36, 45, 12, 94) (5, 26) (56, 25, 37, 69)


Table 15.3: Equations a(x+u1 )·(x+u2 ) = (y +v1 )·(y +v2 ) from x+ay +b
represented by (a, b) (u1 , u2 , v1 , v2 )




© 2009 by Taylor and Francis Group, LLC
452 Algorithmic Cryptanalysis

in [JLSV06].
The main di¬erence between the basic algorithm of Section 15.2 and the
variation we are now presenting is the choice of the smoothness bases. Instead
of considering only linear polynomials, we now consider polynomials of degree
D. When p remains expressed as LQ (1/3, θ) as the size of the ¬nite ¬eld
grows, we choose for D a ¬xed constant. In that case, the analysis is very
similar to the case D = 1.
However, when p is smaller than that, i.e., when:
2/3
log(p) = o(log(Q)1/3 log log(Q) ),

we should make a careful choice for D. In fact, we write:

log(LQ (1/3, θD ))
D= . (15.17)
log(p)

Note that thanks to the o(1) in Equation (15.2) de¬ning the L notation, we
can round D to the nearest integer without changing Equation (15.2).
In addition to controlling the size of the smoothness bases, the parameter
D also changes the algorithm of Section 15.2 in other places. First, it modi¬es
the set of polynomials we consider. Instead of looking at polynomials xy +
ax + by + c, we generalize to polynomials of the form a(x) + b(x)y where a
and b are coprime univariate polynomials of degree at most D in x. Indeed,
if a and b are not coprime, we can factor out the common factor and obtain
another equation of the same form. Thus, when a and b are not coprime, we
obtain duplicates of existing equation. With such polynomials a and b, we now
see that when substituting y by f1 (x) we obtain a polynomial of degree (at
most) D + d1 , where d1 = deg(f1 ). When substituting x by f2 (y), we obtain
a polynomial of degree Dd2 , where d2 = deg(f2 ). Clearly, we should try to
minimize the sum of the two degrees, while keeping d1 d2 ≈ n. Asymptotically,
the optimal choice is to have:

d1 = nD and d2 = n/D. (15.18)

With this choice, we have the degree on each side is approximately d1 . Since
n = log(Q)/ log(p), we see that:
√ 1/3
log(LQ (2/3, θD )) 1 log(Q)
and d2 = √
d1 = . (15.19)
log(p) log log(Q)
θD

As usual the logarithm of the probability of splitting into irreducible poly-
nomials of degree at most D on both sides is approximately:

2
’(2d1 /D) log(d1 /D) = LQ 1/3, ’ √ . (15.20)
3 θD



© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 453

In order to make sure that we obtain enough equations, we remark that we
have LQ (1/3, θD ) polynomials in the smoothness bases and that the size of
the search space a(x) + b(x)y is LQ (1/3, 2θD ). As a consequence, we need :
2
θD = √ . (15.21)
3 θD

This condition implies θD = (2/3)2/3 . Note that making this speci¬c choice
also balances the runtime complexities of ¬nding the equations and solving
the linear system. We leave the adaptation of the individual logarithms com-
putation as an exercise.
With this generalization, the complexity of computing discrete logarithms in
arbitrary ¬nite ¬elds FQ , with Q = pn and p = o(LQ (1/3)), is LQ (1/3, 2θD ) =
3
LQ 1/3, 32/9 . This generalization is a simpli¬cation of the function
¬eld sieve Algorithm [Adl94]. The important aspect of this simpli¬cation is
that, as in Section 15.2, we are directly working in two di¬erent representa-
tions of the ¬nite ¬eld: each element can be expressed either as a polynomial
in x or as a polynomial in y. In general, the function ¬eld algorithm makes
use of a more complicated mathematical structure than polynomial rings:
function ¬elds.


15.3.1 Overview of the regular function ¬eld sieve
Despite the fact that function ¬elds can be avoided altogether for the com-
putation of discrete logarithms in small characteristic, it is interesting to look
at the function ¬eld sieve in order to introduce some of the technicalities that
are needed in larger characteristic with the number ¬eld sieve. When com-
paring the function ¬eld sieve with our previous approach, the ¬rst di¬erence
is that we break the symmetry between the two unknowns that appear in the
algorithm. To emphasize this breach of symmetry, we rename the unknowns
t and X instead of x and y. The function ¬eld sieve is based on the following
commutative diagram:
Fp [t, X]

Fp [t,X] Fp [t,X]
(15.22)
(F1 (t,X)) (F2 (t,X))

Fp [t]
FQ = (g(t))

Looking at the bottom line of this diagram, we see that t plays a special role
because it is used to generate our representation of FQ . On the contrary, X is
no longer used to generate FQ . The middle line of the diagram shows another
crucial di¬erence, instead of removing one of the unknowns on each side, we
keep both and consider all polynomials modulo a bivariate polynomial either
Fp [t,X]
F1 (t, X) or F2 (t, X). From a mathematical point-of-view, (F1 (t,X)) is a ring.




© 2009 by Taylor and Francis Group, LLC
454 Algorithmic Cryptanalysis

If in addition, F1 (t, X) is an irreducible polynomial, this quotient becomes
an entire ring and we can form its ¬eld of fractions. This ¬eld of fractions is
called a function ¬eld. We already introduced such a mathematical object in
Chapter 14.
In the most general case, F1 and F2 can be arbitrary irreducible polynomials
in t and X. In order to make the above diagram commutative, we need the
two simultaneous conditions F1 (t, X) = 0 and F2 (t, X) = 0. Eliminating X
from these two algebraic equations in two unknowns, we obtain an equation
G(t) = 0. If G has an irreducible factor g of degree n, such that pn = Q, we
can keep F1 and F2 as an implicit de¬nition of FQ . In practice, this general
setting is rarely needed and one polynomial is usually chosen of a simpler
form. A typical choice is the following:
D
(i)
f2 (t)X i .
F1 (t, X) = X ’ f1 (t) and F2 (t, X) =
i=0

In other words, we view both F1 and F2 as polynomials in X whose coe¬-
cients are polynomials in t. The ¬rst polynomial f1 is simpler since it is a
linear polynomial. With this speci¬c choice, several simpli¬cations appear.
First, G can now be computed without using resultants, more precisely, we
have G(t) = F2 (t, f1 (t)). Second, the commutative diagram becomes simpler,
because on the F1 side, also called the linear side, with can remove X com-
pletely, replacing it by f1 (t). Thus, on the linear side, we only need to factor
polynomials and the technical di¬culties related to the use of function ¬elds
only appear on the side of F2 .
With this setup, we are now ready to explain how the equations are gener-
ated with the function ¬eld sieve. In order to produce the equations, we start
from linear polynomials in X of the form a(t) + Xb(t). On the linear side,
this becomes a(t) + f1 (t)b(t) with can easily be factored. On the function
¬eld side, matters are more di¬cult. Indeed, unique factorization is not even
guaranteed on that side. As a consequence, we need to decompose a(t)+Xb(t)
into a product of prime ideals in the function ¬eld4 .
Informally, in this context, an ideal I in the function ¬eld is a set of elements
of the function ¬eld such that:

I + I ‚ I and
H(x, T )I ‚ I, for all polynomial H ∈ Fp [t, X]. (15.23)

An ideal is prime if it cannot be decomposed into a non-trivial product of
ideals. Thanks to the fact that a(t) + Xb(t) is linear in X, we only need to

4 InChapter 14, we give a complete description of function ¬elds of a special kind. More
precisely, using the unknowns t and X, this chapter fully describes the function ¬eld of the
curve associated with the irreducible polynomial X 2 ’ t3 ’ at ’ b. In truth, decomposing
an ideal as a product of prime ideals is equivalent to writing the divisor of a function.




© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 455

consider prime ideals of a special form. These prime ideals correspond to a
pair (q(t), X ’ r(t)), where q(t) is an irreducible polynomial modulo p and
r(t) a root of F2 modulo q(t), i.e., F2 (t, r(t)) is a multiple of q(t).
Testing whether a(t) + Xb(t) can be decomposed into a product of prime
ideals of this form is achieved by checking if the numerator of F2 (t, ’a(t)/b(t))
is a product of polynomials of small enough degree. Thus, in practice, gen-
erating the equations with the function ¬eld sieve is not really more di¬cult.
Interpreting the equations in the ¬nite ¬eld is more delicate: it is not clear
at all that an ideal in the function ¬eld can be sent to a element of the ¬nite
¬eld. Indeed, in general, an ideal is not generated by a single element. How-
ever, with function ¬elds, this di¬culty can in fact be ignored. We simply
write the equations in logarithmic form without worrying about the images
of ideals in the ¬nite ¬eld and everything works out. We will see that with
the number ¬eld sieve, the situation is more complicated and that we need
additional tools to obtain a working algorithm.




15.4 Introduction to the number ¬eld sieve
The basic number ¬eld sieve algorithm can be used for two main purposes:
to factor composite numbers N or to compute discrete logarithm modulo a
prime p. The overall outline of the algorithm is identical, however, at the
detailed level there are some important di¬erences. In all cases, the number
¬eld sieve algorithm relies on the following commutative diagram:

Z[X]

Z[X] Z[X]
(15.24)
(f1 (X)) (f2 (X))

Z
NZ

where N is either the composite to factor or a copy of the prime p. As in the
case of the function ¬eld sieve, f1 and f2 are chosen to make sure that the
diagram commute. In the context of the number ¬eld sieve, this means that f1
and f2 have a common root modulo N and thus that N divides the resultant
of the two polynomials as explained in Chapter 11. The above commutative
diagram is valid in the most general case with f1 and f2 of arbitrary degrees.
However, very frequently, f1 is a polynomial of degree 1, f1 (X) = X ’± where
± is a root of f2 modulo N . In that special case, we say that f1 de¬nes a linear
side and we can replace (fZ[X] by Z in the above commutative diagram. As
1 (X))
with the function ¬eld sieve, equations are generated by looking at the images
of elements from the top of the diagram, both on the left- and the right-
hand sides. In all generality, we may consider polynomials of arbitrary degree




© 2009 by Taylor and Francis Group, LLC
456 Algorithmic Cryptanalysis

in Z[X]. However, in the most frequent cases, we restrict ourselves to linear
polynomials of the form a+bX, where a and b are, of course, coprime integers.
On the rational side, the image of a + bX simply is the integer a + b±. On the
right-hand (algebraic) side, the image is the algebraic number a + bβ, where
β denotes a complex root of the polynomial f2 .
Any element a+bX whose images a+b± and a+bβ can both be decomposed
into small enough factors, yields an equation which can be interpreted in
Z/N Z. Note that, as in the case of the function ¬eld sieve of Section 15.3.1,
this interpretation is not always straightforward and requires a careful analysis
of the underlying mathematical structure.
We give a sketch of a description for the number ¬eld sieve in Section 15.4.2.1.
However, for a complete description, we refer the reader to [JLSV06] and [LL93].


15.4.1 Factoring with the quadratic sieve
Before looking at the number ¬eld sieve algorithm and its application to
factoring and discrete logarithms computations, it is useful to review simpler
special cases. The simpler situation that can be imagined involves two linear
sides. It can be achieved by choosing f1 (X) = X and f2 (X) = X + N . In
that basic case, looking at the restricted set of values a + bX with b = 1, we
are simply looking at relations a ≡ a + N (mod N ). In that case, if both a
and a + N decompose into products of primes, all smaller than a smoothness
bound B, we get a multiplicative relation between two products of primes.
This approach is called the linear sieve. We leave its detailed analysis as an
exercise for the reader.
Looking beyond the linear sieve, the next step is to choose a linear poly-
nomial for f1 and a quadratic polynomial for f2 . When N is a composite

that we want to factor, let R be the nearest integer to N and let f2 be the
polynomial:
f2 (x) = x2 + 2Rx + (R2 ’ N ). (15.25)
We can see that coe¬cients of f2 are not too large. More precisely, they are

of the order of O( N ). Since ’R is a root of f2 modulo N , it is natural to
choose for f1 the polynomial:

f1 (x) = x + R. (15.26)

With this choice, we are now ready to generate multiplicative equations.
At this point, the quadratic sieve slightly di¬ers from our general framework.
We may remark that for any integer a, we have:

f1 (a)2 ≡ f2 (a) (mod N ). (15.27)

Thanks to the square on the left-hand side of this equation, we do not need
to factor f1 (a) but only to look at the decomposition of f2 (a). The quadratic
sieve algorithm is parametrized by two values A and B. The parameter A




© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 457

¬xes the range [’A, A] of values of a we consider. The parameter B is a
bound on the size of small primes. When f2 (a) (or its absolute value) factors
into primes smaller than B, we write an equation:
na (a)
ei
2
f1 (a) ≡ pc(a) (mod N ), (15.28)
i
i=1

(a)
where na is the number of primes in the equation, ci is the number of the i-th
(a)
prime involved in the equation and ei is its multiplicity. Note that it is useful
to add an additional element to our list of primes, p0 = ’1. This value of p0
o¬ers a convenient way a representing the sign of f2 (a). We denote by NB
the total number of primes that may appear in the equations, including the
additional p0 . Another interesting remark about the equations, is that since
f2 (a) is a number of the order of 2aR, as long as a remains small compared
to R, the number of primes involved in each instance of Equation (15.28)
remains small.
Once NB (or a few more) equations are found, we construct a Boolean
matrix M . Each line of the matrix corresponds to an instance of Equa-
tion (15.28); each column to a prime from p0 to pNB ’1 . For a line l, we
denote by al the value of a that generates the corresponding equation. On
this line, in the column corresponding to pc(al ) (for each possible value of i) we
i
(a )
ci l
write the value (mod 2). Since the number of primes in each equation is
small, the matrix M is a sparse matrix. Once M is constructed, we search for
a sum of lines equal to zero in F2 . This can be done by ¬nding a non-trivial
element of the kernel of M . Given such an element of the kernel, we can
compute the corresponding sum of lines over the integers and the product P
(modulo N ) of the values f1 (al ) for the lines l included in the sum. Clearly,
the sum yields a vector in which each coordinate is even. Let V denote the
vector where each coordinate is halved. Putting everything together, we see
that:
2
NB +1
pVi
P2 ≡ (mod N ). (15.29)
i
i=0

We recall from Section 2.3.3.1 that two di¬erent square roots of the same
number modulo N can be used to generate a square root of 1 and that random
square roots of 1 modulo N can factor N with probability 1/2 or more.


15.4.2 Discrete logarithms with the Gaussian integer method
The quadratic sieve as presented in Section 15.4.1 relies on the speci¬c
property that a congruence of square is su¬cient for factoring. It is thus
natural to wonder whether the special cases which make things simpler for
factoring also apply for discrete logarithm computations. Clearly, the most
special case of the linear sieve can be applied. Thus, we are left to consider




© 2009 by Taylor and Francis Group, LLC
458 Algorithmic Cryptanalysis

whether the next step with a linear polynomial and a quadratic polynomial
is applicable. In fact, it is and we proceed as follows: ¬rst, we choose a small
positive integer d > 0 such that ’d is a quadratic residue in Fp . Let R be
a root of ’d modulo p. We know from Chapter 2 that R can be written as

R ≡ A/B (mod N ) with A and B of the order of p. With this choice, we
can now let:
f1 (X) = A ’ BX and f2 (X) = X 2 + d. (15.30)
We see that R is a root of both f1 and f2 modulo N . As usual, we take
elements a + bX and see how they can be sent into the sides de¬ned by f1 and
f2 . Clearly, since f1 is linear, this side should be simple. Indeed, replacing X
by A/B in a + bX we ¬nd that the left-hand image is (aB + bA)/B. Since
B is a ¬xed value, we factor aB + bA as a product of primes and when
the factorization is acceptable, we consider B as additional prime which is
included in all equations with exponent ’1.
The side of f2 is slightly more complicated. Since f2 (X) = X 2 + d, the

quotient ¬eld of Z(X)/(f2 ) is the number ¬eld Q[ ’d] obtained by adjoining
to Q (one of) the purely imaginary square root of ’d. This speci¬c kind of
number ¬eld is called an imaginary quadratic ¬eld. In addition, when d = 1, 2,

3, 7, 11, 19, 43, 67 or 163, the ring of integers Q[ ’d] is a unique factorization
domain. As a consequence, in these nine special cases, the quadratic side√
essentially behaves as a linear side. The image of a + bX, i.e., a + b ’d can
be factored into a product of primes. For the sake of completeness, it is useful

to describe the set of primes in Q[ ’d]; they are of two types. The ¬rst type
is simply prime integers such that ’d is a non-quadratic residue modulo . √
Note that most of these primes cannot occur in the factorization of a + b ’d
when a and b are coprime, as a consequence, they can safely be excluded from
the smoothness basis. The second type of primes is obtained by decomposing
the prime integers such that ’d is a quadratic residue modulo as:
√ √
a + b ’d a ’ b ’d
·
= . (15.31)
2 2
The two primes appearing in this equation are complex conjugates of each
other. Note that a /b and ’a /b are the two square roots of ’d modulo .
Once we have the list of primes, assuming that d is one of the nine above

cases and not equal to 1, a + b ’d can be written up to sign as a product
of primes. Thus, adding an additional “prime” 0 = ’1 we ¬nd ourselves
exactly in the situation of the linear sieve. When d = 1, the situation is

slightly di¬erent, a + b ’d can be written as a product of primes multiplied

by either 1, ’1, i or ’i where i denotes ’1. Thus we need to add 0 = i.
Remark that 0 occurs with exponent 0, 1, 2 or 3 in the decomposition. From
a mathematical point-of-view, we see that in both cases 0 generates the unit

group in Q[ ’d]. Indeed, with imaginary quadratic ¬elds, the unit group is
either {1, ’1} when d = 1 or {1, i, ’1, ’i} when d = 1.

The only remaining step to deal with Q[ ’d] in the unique factorization

domain case is to explicitly compute the factorization of a + b ’d. We ¬rst




© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 459
√ √ √
when (a + b ’d)/2 divides a + b ’d, √ then (a ’ b ’d)/2
remark that √ √
divides a ’ b √’d. Thus, divides (a + b ’d) · (a ’ b ’d)√ a2 + db2 , the
=
norm of a + b ’d. Conversely, if p divides the norm of a + b ’d then either
√ √ √
(a +b ’d)/2 or (a ’b ’d)/2 divide a+b ’d. To distinguish between the
two cases, it su¬ces to test whether a/b is equal to a /b or ’a /b modulo .
Remarking that when a and b are coprime, two conjugate primes cannot both
√ √
divide a + b ’d, we see that the multiplicity of a prime a + b √ in the ’d
decomposition is equal to the multiplicity of in the norm of a + b ’d.
Once we have written down exact multiplicative equalities modulo p, be-

tween (aB + bA)/B and a + b ’d, we proceed to compute discrete logarithms
as in Section 15.3. More precisely, taking logarithms, we obtain linear rela-
tions between the logarithms of all primes5 modulo all prime factors Q of
p ’ 1. Once we have enough relations, we can solve the linear system to ob-
tain logarithms of primes. Note that as usual small prime factors of p ’ 1
do not need to be addressed by this method, but can be dealt with using a
generic algorithm with square root complexity.
When none of ’1, ’2, ’3, ’7, ’11, ’19, ’43, ’67 and ’163 is a quadratic
residue in Fp , it is no longer possible to directly work with a unique factoriza-
tion domain. Of course, only a small proportion of primes (approximately 1
in 512 primes) are of this bad form. However, it is interesting to see how this
di¬culty can be overcome. In this√ case, we need to proceed with a value of d
such that the ring of integers of Q[ ’d] is not a unique factorization domain.

For example, in Q[ ’5] we may see that:
√ √
6 = (1 + ’5) · (1 ’ ’5) = 2 · 3, (15.32)

and√ that the prime 2 does not have any not trivial divisor and divides neither

1 + ’5 nor 1 ’ ’5. As in the case of the function ¬eld sieve, we now need

to factor the elements a + b ’d into products of prime ideals. For example,
the equality in Equation (15.32) corresponds to a decomposition of the ideal

2+
generated by 6 into a product I2 I3 and I3 , where each of √ three ideals is
the
√ +
generated by two elements, 2 and 1 + ’5 for I2 , 3 and 1 + ’5 for I3 , 3 and
√ ’
1 ’ ’5 for I3 . None of these ideals can be generated by a single element.
Without going into the theory of ideals in number ¬elds or even quadratic
¬elds, let us say that the set of ideals forms an abelian group. Moreover, in
this group we ¬nd a subgroup formed of ideals which can be generated by
single elements, called principal ideals. The quotient of group of ideals by
the subgroup of principal ideals is called the ideal class group of the number
¬eld. It is a ¬nite group and its cardinality k is called the class number of
the number ¬eld. A consequence of this is that the k-th power of any ideal
is always a principal ideal. As a consequence, up to multiplication by a unit,

i.e., up to sign, the k-th power of any a + b ’d in a imaginary quadratic ¬eld

5 Including the special “primes” corresponding to B and to the units in the quadratic imag-
inary ¬eld.




© 2009 by Taylor and Francis Group, LLC
460 Algorithmic Cryptanalysis

can be written as a product of k-th power of prime ideals, i.e., as a product of

elements which generates these ideals. Going back to our example in Q[ ’5],
we have a class number k = 2 and we can ¬nd generators for the squares of
2
the ideals appearing in the decomposition of 6. More precisely, I2 is generated
√ √
+2 ’2
by 2, I3 by 2 ’ ’5 and I3 by 2 + ’5.
Thus, for all quadratic imaginary ¬elds, we can write explicit multiplicative

equations between the k-th powers of (aB+bA)/B and a+b ’d. When taking
the logarithm of such equations, we can clearly factor k out. Moreover, if the
linear algebra is to be done modulo Q, we can in fact divide the equations
by k as long Q and k are not coprime. Since Q is a large prime divisor of
p ’ 1, it is clear that Q and k are coprime unless we get extremely unlucky.
With this process we can associate with any prime ideal a value equal to the
logarithm of a generator of the k-th power of this ideal divided by k. For
convenience, we call this value the virtual logarithm of the ideal. A ¬nal
important remark is that when computing modulo an odd prime Q, the units
in the quadratic imaginary ¬eld can altogether be ignored. Indeed, since their
order is either 2 or 4, their discrete logarithm modulo Q is necessarily equal
to 0.
Note that to compute arbitrary discrete logarithm, we need to adapt the
descent method for this case.

15.4.2.1 Obstructions to the number ¬eld sieve
Taking the quadratic sieve as a model, we may try to generalize it to ar-
bitrary number ¬elds. That is, given a polynomial f2 irreducible over Q[X],
we can consider the number ¬eld obtained as quotient ¬eld of Z[X]/(f2 ) and
denoted Q[β], where β is a complex (potential real) root of f2 . We are inter-
ested by the possible factorizations of elements a + bβ. In general, as in the
general quadratic case, we are not in a unique factorization domain and we
can decompose a + bβ into a product of prime. However, we can write it as
a product of prime ideals. Moreover, for a general number ¬eld, we also have
a ¬nite class number k and looking at k-th powers, we may write an ideal
equality between two products, one on the linear side and the other in the
number ¬eld. Thus, at ¬rst, it may seem that going to the number ¬eld sieve
for discrete logarithm computations does not require any new tool. However,
this ¬rst impression is not correct. The problem is that when two integral el-
ements x and y in a number ¬eld generate the same ideal, we cannot say that
x = y but only that there exists a unit u such that x = uy. With imaginary
quadratic ¬elds, all units had ¬nite order 2 or 4 and could easily be dealt with.
With arbitrary number ¬elds, there exists unit of non-¬nite order which can-
not be removed when working modulo Q. This is the most important problem
that needs to be overcome in order to use arbitrary number ¬elds in index
calculus.
When factoring with the number ¬eld sieve, there are in fact two potential
obstructions. Clearly, the obstruction coming from units remains, but in




© 2009 by Taylor and Francis Group, LLC
Index calculus algorithms 461

addition, we cannot ignore the class group. Indeed, in the case of factoring,
we want to compute the linear algebra modulo 2 and we cannot have any
guarantee that the class number k is invertible modulo 2, i.e., odd. One way
out of this problem would be to restart the computation with another number
¬eld should a problem occur. Since we expect an odd class number about half
of the time, this would on average double the running time. However, this is
not necessary. Instead, it su¬ces to add extra terms in the equations we are
writing to get rid of the obstruction. These extra terms are computed using
either characters [LL93] or Schirokauer™s maps [Sch93].


15.4.3 Constructing number ¬eld sieve polynomials
The number ¬eld sieve is too complex to develop in details here. Instead,
we refer the reader to [LL93] and [JLSV06] for complete descriptions in all
accessible ¬nite ¬elds. However, the question of constructing polynomials f1
and f2 for number ¬eld sieve algorithms is easily accessible with the tools we
have at hand. We ¬rst analyze theoretical bounds on the sizes of coe¬cients
that can be achieved for these polynomials and then present the simple base
m construction.

15.4.3.1 General setting
Throughout this section, we denote by d1 the degree of f1 and by d2 the
degree of f2 . We further write:
d1 d2
(1) (2)
Ci X i Ci X i .
f1 (X) = and f2 (X) =
i=0 i=0

To optimize the e¬ciency of the sieving step with these polynomials, we
need to minimize the size of the smooth numbers we need to ¬nd while sieving.
These numbers are norms of linear number ¬eld elements obtained from a+bX.
For simplicity, we assume that we are in the balanced case where a and b are
chosen in a half-square, with 0 < a ¤ S and ’S ¤ b ¤ S. In this balanced
case, since the norm on each side respectively is:
d1
(1)
Ci (’a)i bd1 ’i and
d1
b f1 (’a/b) = (15.33)
i=0
d2
(2)
Ci (’a)i bd2 ’i ,
d2
b f2 (’a/b) = (15.34)
i=0

it is natural to have all coe¬cients in f1 of roughly the same size C1 and all
coe¬cients in f2 of size C2 .
Since f1 and f2 have a common root modulo N or p but not over C, the
resultant of f1 and f2 is necessarily a multiple of N , resp. p. Since the resul-
tant is the determinant of a matrix that contains d2 copies of the coe¬cients




© 2009 by Taylor and Francis Group, LLC
462 Algorithmic Cryptanalysis
d d
of f1 and d1 copies of the coe¬cient of f2 , its order of magnitude is C1 2 C2 1 .
Thus, d2 log2 (C1 ) + d1 log2 (C2 ) is of the order of log2 (N ) or larger.
Moreover, the above property shows that f1 and f2 form an encoding of N in
the information theoretic sense: given f1 and f2 we can retrieve N or at least
a small set of candidates containing N . Since N is essentially an arbitrary
number, there should not exist any short encoding of N . As a consequence,
the sizes of the coe¬cients C1 and C2 cannot be too small. More precisely, we
expect that (d1 + 1) log2 (C1 ) + (d2 + 1) log2 (C2 ) is near to log2 (N ) or larger.

<<

. 16
( 18)



>>