ńņš. 16 |

(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)

3Īø

since log(d) ā log(Q)/3. Thus, the balance condition becomes:

2

2 2 3

3

Īø = ā or Īø = = 4/9. (15.11)

3

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

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 |