Discrete logarithm over finite fields of "small" characteristic

(1)

Facolt`

a di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea Magistrale in Matematica

Tesi di Laurea

Discrete logarithm in finite fields

of small characteristic

Candidato

Relatore

Correlatore

Guido Maria Lido

Prof. Ren´

e Schoof

Prof. Roberto Dvornicich

(2)

Introduction

Given a group G and two elements g, h ∈ G, solving the discrete logarithm problem consists of finding an integer x ∈ Z such that

gx= h

if it exists. Its connection to many cryptographic protocols has motivated a large amount of research intended to find efficient algorithms to solve this problem for special groups, like the group of rational points of an elliptic curve over a finite field or the group of invertible elements of a finite field.

Among these cryptographic protocols some are very general and can be imple-mented in every group, while others are more specific: for example, the security of the digital signature standard is based on the assumption that the discrete loga-rithm problem is computationally hard for the multiplicative groups of finite fields of prime order. The study of the discrete logarithm problem over finite fields of “small” characteristic has become important since the use of pairing attacks on the discrete logarithm problem for elliptic curves.

Recently the work of A. Joux has led to algorithms heuristically faster than the previous ones for the discrete logarithm problem over finite fields of small char-acteristic, i.e. fields of prime characteristic p and cardinality pn _{for some n > p.}

This progress is the central topic of the thesis: we study the connection of the new algorithms with the previous ones and we show how the new ideas can be used to rigorously prove that the complexity of the discrete logarithm problem in small characteristic is at most quasi-polynomial.

In the first chapter we analyze classical algorithms that fall in the category of the index calculus whose complexity has the form

Lpn[α, c] := exp{(c + o(1))(log pn)α(log log pn)1−α}

for real numbers c > 0, and α ∈ (0, 1) (sub-exponential complexity). The common idea of these algorithms comes from the Morrison-Brillhart factorization method and consists of seeking for polynomials with irreducible factors of small degree. In particular, their analysis needs estimates of this probability in specific situations.

We look at the simplest algorithm of index calculus in two different forms: the first one to show clearly the ideas, the second to make rigorous analysis and prove that the expected running time is Lpn[1

2, c]. Then we turn our attention to the

function field sieve which is a family of algorithms of complexity Lpn[1

3, c]. We

focus on the algorithm presented by Coppersmith in 1984, that could be seen as a “father” of the actual function field sieve, published by Adleman ten years later. This choice is motivated by the resemblance between Coppersmith’s and Joux’s

(5)

4 INTRODUCTION

algorithms.

In the second chapter we look at the recent developments. We analyze the ideas contained in Joux’s article “A new index calculus algorithm of complexity Lpn[1

4, c]

in small characteristic” and we see how these ideas lead to a quasi-polynomial al-gorithm, i.e. an algorithm having complexity exp{O ((log log pn₎c_{)} for some c > 0.}

Indeed, in 2014 Joux together with Barbulescu, Gaudry and Thom´e has published an article that, under some heuristic assumptions on the probability of certain families of polynomials to be factored in terms of polynomial of “smaller degree”, solves the discrete logarithm problem in quasi-polynomial time on every finite field admitting a certain kind of presentation.

Then we analyze another quasi-polynomial algorithm published by Granger, Kleinjung and Zumbr¨agel (GKZ) based on the same ideas: this algorithm can be rigorously analyzed and proves without any heuristic assumption that the discrete logarithm problem has at most quasi-polynomial complexity on every finite field admitting that certain kind of presentation.

The last chapter contains the original part of the thesis: we define another kind of presentation for finite fields of small characteristic similar to the one seen in the second chapter and we describe a new version of Granger’s algorithm adapted to this setting. Using the classical theory of elliptic curves over finite fields we prove that any finite field of small characteristic can be embedded into a slightly larger field that admits a presentation of this new type. Thus our algorithm can be applied to solve the discrete logarithm problem for every finite field of small characteristic and can be proved to run in quasi-polynomial time. At the moment we unfortunately only have a partial proof of the correctness of our algorithm: we reduce it to the proof of two similar technical statements and we give a full proof of one of these two statements with the use of some intersection theory and of the Riemann hypothesis for curves over finite fields. We expect that the other statement is provable by similar arguments, despite the difficulties in the calculations.

(6)

CHAPTER 1

Index calculus algorithms

Given a finite field K of order pn _{and two elements g, h ∈ K}∗ _{solving the}

discrete logarithm problem on K means either find an integer x (mod pn_{− 1) such}

that

gx= h or proving that h /∈ hgi.

Many algorithms intended to solve this problems can be applied also on a group other than K∗: this is the case of the Baby Step-Giant Step algorithm, that re-quires to compute O(pn2) powers of g or the case of Pollard’s rho method requiring

a comparable running time; the same holds for Silver-Pohlig-Hellman’s algorithm, convenient if all the irreducible factor of pn− 1 are small, to exploit the fact that K∗ is the product of cyclic groups whose orders are powers of small primes.

Other algorithms, independently of the factorization of pn− 1, are asymptot-ically faster than any exponential algorithm (i.e. an algorithm whose complexity is O ((pn₎α_{) for some α > 0, like the Baby Step-Giant Step); all these algorithms}

are specific for finite fields or even specific for some finite fields. In this thesis we are concerned only with finite fields with characteristic “small” if compared to the order, that is we deal only with the cases where n > p; moreover while it is not the only interesting case we suppose every time that g generates K∗. In this chapter we analyze the most studied class of sub-exponential algorithms, the algorithms of index calculus; all these algorithms rely on the “high” probability of a random polynomial of degree d to be factored in terms of irreducible polynomials of degree less than d0 for some d0 of the right “small” size with respect to d. Thus it is useful to give the following

Definition. Given a positive integer m, a field K and a polynomial f ∈ K[x] we say that f is m-smooth over K if every irreducible factor of f in K[x] has degree less or equal than m.

Before analyzing some algorithms of index calculus we need some results es-timating how many a polynomials of degree n defined over a finite field K are m-smooth, for different triples (K, m, n).

1. Smoothness probability of polynomial over finite fields

Given a field K with q elements and two positive integers m ≤ n, we want to give an estimate of the number

NK(n, m) = #{f ∈ K[x] : deg f = n, f is m-smooth over K}. 5

(7)

6 1. INDEX CALCULUS ALGORITHMS

The probability of a polynomial in K[x] of degree n to be m-smooth is defined to be PK(n, m) = NK(n, m) NK(n, n) =NK(n, m) qn_{(q − 1)}.

For example one can easily estimate this probability when m = 1: a monic polynomial of degree n with coefficient in K completely determined by its roots, thus the completely factored polynomials of degree ≤ n over K are

NK(n, 1) = (q − 1) n + q − 1 q − 1 = (q − 1) n Y i=0 q + i i + 1 = qn(q − 1) n! n Y i=0 1 + i q . We deduce that 1 n! ≤ PK(n, 1) ≤ 1 n!exp{ n(n − 1) 2q }

and consequently if n is fixed and #K → ∞ then PK(n, 1) ≈ (n!)−1.

A very general result about the asymptotic behavior of P(n, m) when both m, n

are large and m log n is contained in [FGP]. To state it in full generality we need the following

Definition. The Dickman function ρ(u) is the unique continuous solution on [0, +∞] of the “functional differential” equation

ρ(u) = 1 ∀u ∈ [0, 1] uρ0(u) = −ρ(u − 1). We need to know that ρ(u) ∼ u−u for u → ∞.

The general result we referred to before has been proved by Panario, Gaudron and Fajolet in [FGP] using analytic methods and is the following

Theorem 1. For any finite field K, the probability of a polynomial in K[x] to be m-smooth of degree n satisfies

PK(n, m) = ρ n m 1 + O log n m

where the big O is uniform in K.

We mainly apply this theorem to study PK(m, n) when m, n tend yo ∞ growing

at different “rates”. To explain this, let us define a new class of functions. Definition. Given c ∈ R+, α ∈ (0, 1), we define the class of functions

Lx[α, c] = exp{(c + o(1)) (log x)α(log log x)1−α}.

Given a function f : R+_{→ R}+_{we write f ∈ L}

x[α, c] if there exist f1, f2: R+→ R+

tending to 0 when x → ∞ such that

exp{(c − f1(x)) (log x)α(log log x)1−α} ≤ f (x) ≤ exp{(c + f2(x)) (log x)α(log log x)1−α}. Moreover we denote by Lx[α] the union of Lx[α, c] for c > 0.

This class of functions appears often in index calculus algorithm, both when defining variables inside the algorithm and when analyzing the running time; when working on a field of order pn we encounter functions of two variables φ(p, n) that in the cases of interest (i.e. when pn _{is the cardinality of a finite field on which}

(8)

1. SMOOTHNESS PROBABILITY OF POLYNOMIAL OVER FINITE FIELDS 7

below by functions in Lx[α, a] computed in x = pn. In this case, with little abuse

of notation we write φ(p, n) ∈ Lpn[α, a].

Let us now state a result often recurring in the analysis index calculus algo-rithms.

Proposition 1. Given 0 < β < α ≤ 1, a, b > 0 and two functions φ1(p, n) ∈

Lpn[α, a], φ₂∈ L_pn[β, b] one has

P_Fp logp(φ1(p, n)) , logp(φ2(p, n))

−1

∈ Lpn[α − β, (α − β)

a b].

Proof. It is a simple matter of computation; we use big O, small o notation implying that the we consider the limit for pn _{→ ∞. In particular for this notation}

log_pφ1(p, n) = (a + o(1)) (log p)−1(log pn)α(log log pn)1−α

log_pφ2(p, n) = (b + o(1)) (log p)−1(log pn)β(log log pn)1−β

log_pφ1(p, n)

log_pφ2(p, n)

=a b + o(1)

(log pn)α−β(log log pn)β−α

log _log

pφ1(p, n)

log_pφ2(p, n)

= log(log pn)α−β(1 + o(1)) = (α − β + o(1)) log log(pn). Since

log(log_pφ1)

log_p(φ2)

= (1+o(1)) log(pn)−β(log log pn)α−(1+o(1)) log(pn₎−β_{(log log p)}−1_{= o(1)}

we can apply 1 and deduce that

P_F_p log_p(φ1(p, n)) , logp(φ2(p, n)) = ρ _log pφ1(p, n) log_pφ2(p, n) (1 + o(1)) = = exp −logpφ1(p, n) log_pφ2(p, n) log _log pφ1(p, n) log_pφ2(p, n) (1 + o(1)) = = expn−a b + o(1)

(log pn)α−β(log log pn)β−α(α − β + o(1)) log log(pn)o= = expn−a

b(α − β) + o(1)

(log pn)α−β(log log pn)1+β−αo

.

The result follows from the definition of the L notation. We also need an estimate on PK(n, m), depending only on mn and valid even

in the case m is small compared to n Theorem 1 together with some elementary consideration implies the following estimate; since we do not need a sharp inequality we preferred the following simpler one.

Theorem 2. There exists an absolute constant C > 0 such that for any finite field K and any pair of integers (m, n) with m < 3n one has

PK(n, m) ≥ Cn m −2mn .

Proof. Let C1> 4 be a constant such that PK(n, m) ≥ ρ _mn

1 − C1log n_m

and let C2 be such that ρ(u) ≥ C2−1u−u for every u > 1 (we know that C2 exists).

We prove that C = max{2

(9)

By theorem 1 if 2C1log n ≤ m the estimate is abundant, thus we focus on the

case 2C1log n ≥ m. since we want to express everything with _mn we write here that

for future reference that this equality implies m ≤ 4C2 1log log

n m.

Let q be the cardinality of K, let a = d_mne and let b be such that n = am + b; moreover for every positive integer j let tj be the number of monic irreducible

polynomials of degree j in K[x]; then it is standard that tj > 2j1q

j_{. A particular}

kind of m-smooth polynomials of degree n are the polynomials that are the product of a irreducible polynomials of degree m and one polynomial of degree b; by standard combinatorics the number of polynomials of these kind is

tm+ a − 1 a · tb> ta m a! · tb> qam_qb (2m)a_a!2b > qn (2m)a+1_a!.

It is clear that PKn, m is greater than the probability of a (monic) polynomial of

degree exactly n; thus, using the inequality on m and the fact that a + 1 ≤ _mn + 1 we obtain that PK(n, m) > qn (2m)a+1_a! > 16 eC 2 1log log n m −mn−1n m −mn >Cn m −2mn . 2. The first algorithm of index calculus

The first sub-exponential algorithm for the DLP on Fpn that does not depend

on the factorization of pn_{− 1 was presented by Adleman in [Adl] for the case of}

prime fields and by Hellman and Reyneri in [HR] in the case of fields of “small” characteristic. In both cases the main idea comes from the Morrison-Brillhart factorization method, an algorithm that exploits the high probability of a natural number to be factored in terms of “small” primes. Analogously when computing the discrete logarithm in a finite field of small characteristic one can exploit the “high” probability of a random polynomial of fixed degree to be smooth with respect to some bound Bn “small” if compared to the degree.

Suppose we have described a finite field of characteristic p > 0 as Fp[X]/µ(X)

for some irreducible polynomial µ ∈ Fp[X] of degree n > p, we have been given

two polynomials g, h ∈ Fp[X] such that [g] generates (Fp[X]/µ(X))∗ and h /∈ (µ)

and that we want to find log[g][h]; then in index calculus algorithm one also seek

for log[g]([f ]) for every irreducible f ∈ Fp[X] of degree smaller of some bound

Bn, since it easier to find multiplicative relations involving such polynomials. In

particular index calculus algorithm are often divided in two phases: with the first phase one finds the discrete logarithm (sometimes called “index”) of the classes of the irreducible polynomials of degree ≤ Bn (this set is called factor base); in the

second phase one finds the discrete logarithm of the target element, reducing to the discrete logarithm of the elements of the factor base.

Basic index calculus algorithm, version 1. Takes as input a constant c > 0, a prime number p , an irreducible polynomial µ ∈ Fp[X] of degree n > p

and two polynomials g, h ∈ Fp[X] such that g is a generates (Fp[X]/µ(X)) ∗

and h is not zero. Outputs a natural number x such that gx_{≡ h (mod µ)}

(1) Preparation: Set B ← c

√ n log n √

log p and find all the elements of F = {f ∈

Fp[x] : f monic, irreducible, deg f ≤ B}; set j ← 1, T ← #F and sort all

(10)

2. THE FIRST ALGORITHM OF INDEX CALCULUS 9

(2) Collecting relations: Select a random integer a between 1 and pn− 2 and compute a polynomial f (X) of degree < n such that f ≡ ga (mod µ). If f is not B-smooth, repeat this step; otherwise compute the factorization f = b0Q

T i=1f

bi

i , find a0such that ga0(p

n_{−1)/(p−1)} ≡ b0 (mod µ), set aj← a − a0p n₋₁ p−1 and set b j i ← bi for each i = 1, . . . , T .

If j ≤ 2T then set j ← j + 1 and repeat this step, if j = 2T + 1 go to step 3

(3) Computing the index of the elements in the factor base: If the matrix (bj_i), considered (mod pn_{− 1), has maximal rank find the T −uple (c}

1, . . . , cT)

such that c1bj1+ . . . cTbjT = aj for each j = 1, . . . , 2T + 1

(4) “Smoothing” the target element : Select a random integer a between 1 and pn − 2 and compute a polynomial f ≡ ga _{· h (mod µ) of degree}

< n; if f is not B-smooth then repeat this step; otherwise compute the factorization f = b0Q

T i=1f

bi

i and find a0 such that ga0(p

n_{−1)/(p−1)} ≡ b0 (mod µ). Output x = a0 pn_{− 1} p − 1 + c1b1+ . . . cTbT− a.

Let us now give an heuristic estimate of the running time of the algorithm above.

Step 1 can be performed simply by testing the irreducibility of every monic poly-nomial with degree ≤ B; since the a single irreducibility test on a polypoly-nomial of degree d takes O((d log p)3_{) and we have to consider approximately p}B _polynomials,

then this step requires O(pB_{(B log p)}3_{) operations. Let us recall for future reference}

that p_2BB ≤ T ≤ p_BB.

During a single execution of step 2 one computes a power exponentiation inside Fp[x]/(µ) that takes O (n log p)4 operations and then computes the factorization

of a polynomial of degree < n over Fp that takes average time O(n3p) with

proba-bilistic Berlekamp’s algorithm [Ber]; the other operations are negligible since com-puting the discrete logarithm of an element in F∗ptakes O(p) operations simply by

trials and data storage takes O(n) operations by using sparse matrix representation. Thus a single execution of Step 2 requires averagely O (n log p)4_elementary

op-erations. How many times is step 2 repeated before one goes to step 3? Answering this question is equivalent to guessing how many random polynomials f of degree < n one has to consider before one finds 2T polynomials that are B-smooth; since the probability of f being B-smooth is approximately (_Bn)−Bn thus we expect to

repeat step 2 about 2T (_Bn)Bn times.

Step 3 consists in linear algebra computations in Z/(pn

−1)Z with 2T ×T matrix and requires O (nT log p)3_{operations. We suppose that “most of the time” the}

matrix have maximal rank, i.e. that the third step is repeated a negligible number of time, say polynomial in n log p; in particular we estimate the running time as if the matrix (bj_i) always has maximal rank, supposing that this simplification only reduces the running time of a multiplicative factor that is polynomial in n log p.

Step 4 consists essentially in a power exponentiation in Fp[x]/(µ) and the

fac-torization of a polynomial of degree < n over Fp, just like step 2 and it is repeated

until a single B-smooth polynomial is found, thus the time spent executing step 4 is dominated by the time spent executing step 2.

(11)

Summing up we see that heuristically this algorithm should require

O pBB3log p + 2T (_Bn)nB(n log p)4+ (nT log p)3 operations. Let us define f₁, f₂, f₃

the expressions appearing (in this order) in the big O, in which we substitute T = pB_{/B (it is lecit to do it since T p}B_{/B), and B = c}√_√n log p

log n and ; then as

a function in p, n we see that f1 is bounded from above and also from below by

functions in Llog pn[1

2, c], f2is bounded from above and from below by functions in

Llog pn[1

2, c + 1

2c], f3 is bounded from above and also from below by functions in

Llog pn(3c,1

2).

Thus the heuristic complexity of the algorithm can be bounded both from above and from below by a function in Llog pn[1

2, max{c + 1 2c, 3c}].

If we want to make this analysis rigorous, the main difficulty is giving an estimate of the probability of the matrix (bj_i) being singular; instead of trying to make such estimates we present a modification of the algorithm above. However the algorithm we have just analyzed remains valid for practical implementation and moreover if we want to execute it more than once on the same field we can execute the factor base phase (the second and the third phase) only once.

3. The first rigorous algorithm of index calculus

Let us present an algorithm similar to the last one, but this time we are able to make a rigorous analysis. The ideas are the same of the previous one but the computation of the discrete logarithm of elements in the factor base is in some sense implicit; in this way one does not have to estimate the probability of a matrix having full rank and has more control on the random processes behind the algorithm.

Basic index calculus algorithm, version 2. Takes as input a prime number p , an irreducible polynomial µ ∈ Fp[X] of degree n > p and two polynomials

g, h ∈ Fp[X] such that g is a generator of (Fp[X]/µ(X)) ∗

and h is not multiple of µ. Outputs is a natural number x such that gx_{≡ h (mod µ)}

(1) Preparation: Set B ← c

√ n log n √

log p and find all the elements of F = {f ∈

Fp[x] : f monic, irreducible, deg f ≤ B}; set j ← 1, T ← #F and sort all

the elements f1, . . . , fT ∈ F . Go to step 2

(2) Collecting relations: Select random integers a, b between 0 and pn− 2 and compute a polynomial f ≡ gahb (mod µ) of degree < n; if f is not B-smooth then repeat this step; otherwise compute the factorization f = c0Q

T i=1f

ci

i ; set aj ← a, bj← b and vj= (c1, . . . , cT).

If j ≤ T then set j ← j + 1 and repeat this step, if j = T + 1 go to step 3 (3) Linear algebra: Compute d1, . . . , dT +1∈ {0, . . . , pn− 2} such that

G. C. D.(d1, . . . , dT +1) = 1 and d1v1+· · ·+dT +1vT +1∼= (0, . . . , 0) (mod pn−

1). Set l ← d1a1+ · · · + dT +1aT +1, k ← d1b1+ · · · + dT +1bT +1. Compute

s ∈ F∗p such that hkgl≡ s (mod µ) and compute y such that g

ypn −1_p−1 _{≡ s}

(mod µ).

(4) Finished? : If k is not invertible (mod pn− 1) set j ← 1 and go back to step 2, otherwise output

x ≡ yp n_{− 1} p − 1 − l k−1 (mod pn− 1).

(12)

3. THE FIRST RIGOROUS ALGORITHM OF INDEX CALCULUS 11

To prove the correctness of the algorithm above let us prove that glhk is con-gruent to an element in F∗p. Let v1, . . . , vT +1 the vectors of integers stored at the

beginning of the third step, with coordinates vj(i)’s and let wj be the element in

F∗p such that g aj_hbj _{= w} jQ T i=1f vj(i)

i ; then if k, l are the variables defined in stage

3, using the definition that d1v1+ · · · + dT +1vT +1 ∼= (0, . . . , 0) (mod pn− 1) we

obtain glhk≡ T +1 Y j=1 gaj_hbjdj = T +1 Y j=1 wdj j T Y i=1 fdjvj(i) i ! =   T +1 Y j=1 wdj j   T Y i=1 f PT +1 j=1djvj(i) i ≡ ≡   T +1 Y j=1 wdj j   T Y i=1 (1) = T +1 Y j=1 wdj j (mod µ).

Since the wj’s belong to F∗pwe obtain that at the end of step 3 one can define s and

find y such that gl_hk_{≡ g}ypn −1_p−1 _{. Now it is clear that, if k is invertible (mod p}n_{− 1)}

with inverse k−1 then

gx=gypn −1p−1 _g−l

k−1 ∼

= (hk)k−1 ∼= h (mod µ). Thus if the algorithm finishes, then the output is correct.

Now let us prove that the average running time of the algorithm is in Lpn[1₂]. We

firstly notice that the number of operations needed is not less than the cardinality of the factor base, thus at least _2BpB for B =

√ n log n √

log p . Thus the complexity of

the algorithm above is bounded from below by a function in Lpn[1₂]. Let us now

estimate the running time of each step, then we give an estimate of the average number of time each step is repeated.

Step 1 can be performed testing the primality of every monic irreducible poly-nomial of degree ≤ B and since a single irreducibility test on a polypoly-nomial of degree d takes O(d3log p) and we have to consider approximately pB polynomials, then this step requires O(pBB3log p) operations, thus it is estimated by a function in Lpn[1

2]

Step 2 is analogous to the second step of the algorithm in the previous chapter and takes O (n log p)4_{operation. In fact multiplications and exponentiations to}

a power ≤ n in Fp[X]/µ(X) takes O (n log p)4 operations, factoring can be done

in average time O(n3p) with probabilistic Berlekamp’s factorization algorithm and the vector vj can be stored in O(n) operation using sparse representation.

Step 3 can be done by computing the row echelon form of the matrix in Z(2T +1)×T having as row the vj’s plus all the row of pn − 1 IdT. This can be

done in O((T log pn₎3_{) operation thus estimated by a function in L} pn[1

2].

Step 4 only consists of standard arithmetic modulo (pn _{− 1), thus requires}

O((n log p)3_{) operations.}

To estimate the number of times that each step is repeated we need to calculate the probability that in step 2 the polynomial f is B-smooth and the probability that in the last step the integer number k is invertible (mod pn−1). We talk about prob-ability in the following sense: given countably many independent equidistributed stochastic variables A1, B1, A2, B2, . . . assuming the values 1, 2, . . . , pn − 1 (this

(13)

variables model the random a, b during each execution of step 2) then the execu-tion of the algorithm depends on the output of these variables, thus the running time of the algorithm (or the number of times that a single step is executed) is itself a stochastic variable with an expected value.

For each r ∈ Z> 0 we have that gAr_hBr _{(mod µ) is a random equidistributed}

variable in F[X]/µ

∗

(this comes from the fact that g is a generator) and this is equivalent to saying that f is a “random” non-zero polynomial of degree < n, thus the probability that in step 2 the polynomial f is B-smooth is exactly P_F_p(n − 1, B) that, by proposition 1, is the inverse of a function in Lpn[1

2].

Now consider the (T + 1)-uple (d1, . . . , dT +1) computed during the first

execu-tion of step 3 of the algorithm as a stochastic variable (it is clear that the probability that the algorithm never reach step 3 is 0) and do the same for the(T + 1)-uples (a1, . . . , aT +1), (b1, . . . , bT +1) stored during the same execution of step 3. The (T +

1)-uple (d1, . . . , dT +1) only depends on the polynomials ga1hb1, . . . , gaT +1hbT +1 that

are independent of the variable (b1, . . . , bT +1), thus (b1, . . . , bT +1) and (d1, . . . , dT +1)

are independent. Moreover (b1, . . . , bT +1) is equidistributed on {1, . . . , pn− 1}T +1.

Since (d1, . . . , dT +1) is always a T +1-uple of coprime integers, then the variable k =

d1b1+· · · dT +1bT +1 (mod pn−1) is equidistributed in {1, . . . , pn−1}, thus the

prob-ability that k is coprime to pn_{− 1 is exactly φ(p}n_{− 1)/(p}n_{− 1) ≈ e}−γ_{(log log p}n₎−1_,

where γ is the Eulero-Mascheroni constant.

If we denote by c1, c2, c3, c4 the complexity of the four steps of the algorithm,

recalling that c1, c3, PFp(n − 1, B)

−1_{, T ∈ L} pn[1

2] and c2, c3are polynomial in log p n

and the previous probability estimates, we deduce that the average running time of the algorithm is O c1+ (pn_{− 1)} φ(pn_{− 1)} (T + 1)PFp(n − 1, B) −1_c 2+ c3 + c4 ∈ Lpn[ 1 2].

4. The function field sieve

An improvement to the algorithms above was made by Don Coppersmith in 1984 for fields of characteristic 2, and then generalized to arbitrary fields of small characteristic by Leonard Adleman ten years later: they found algorithms able to solve the DLP on a field of order pn, whose running time lies in Lpn[1

3].

These are still algorithms of index calculus, since they’re success depends on the probability of certain polynomials being smooth (i.e. having small irreducible factors) and since they compute the logarithm of elements in a factor base together with the logarithm of the target element. But this time one does not consider random polynomials, and looks instead for multiplicative relations involving poly-nomials of degree much smaller than before; thus these polypoly-nomials are in general “more factorisable” and this allows to use smaller factor base, reducing the com-plexity.

Let us see how this happens in a generalization of Coppersmith’s algorithm, applied to a field K of arbitrary characteristic p and order pn _{for some integer}

n > p6_.

4.1. The presentation of the field. The first ingredient is a special pre-sentation of the finite field, i.e. an irreducible polynomial µ(X) of degree n of some special kind: this algorithm needs in the input a polynomial ν(x) of degree

(14)

4. THE FUNCTION FIELD SIEVE 13

≤ n13 such that µ(X) = xn− ν(x) is irreducible; the field K is then isomorphic to

Fp[X]/µ(X).

The existence for any p and any n > p6 of such a presentation is not proven, only supported by heuristic arguments like the following. If for any generator α of the extension Fpn/F_p one sets ν_α equal to the only polynomial of degree ≤ n

such that αp_{= ν}

α(α), proving the existence of a presentation `a la Coppersmith is

equivalent to finding α such that deg να≤ n

1

3; if we assumed that ν_αvaries in some

“random way”, then the probability that deg να > n

1

3 for all α would be about

exp{− log p(1 − n−23)pn}, fairly “small” for pn “big”.

We are going to present an algorithm that, given a prime p, an integer n > p6_,

a polynomial ν(X) such that (xn_{− ν(x)) is irreducible and two elements g, h ∈}

(Fp[X]/ (xn− ν(x)))∗computes loggh.

If we had in input a prime p, an integer n > p6_{, an irreducible polynomial µ}0_(X)

of degree n (with no hypothesis on µ0) and two elements g0, h0∈Fp[X]/µ0(X))

∗ , then we could do the following in order to compute log_g0h0:

• consider random polynomials ν(X) of degree ≤ n13 until (xn− ν(x)) is

irreducible; trying all the ν(X) takes a time estimated by a function in Lpn[1

3], however we heuristically expect this time to be much smaller (if

such a ν is not found the algorithm fails). Set µ(X) ← xn− ν(x). • Using the algorithm in [Len], find g, h ∈ (Fp[X]/µ(X))∗ such that there

is an isomorphism (Fp[X]/µ(X)0)∗→ (Fp[X]/µ(X))∗ sending g0 in g and

h0 in h; this can be done in deterministic polynomial time in the input, i.e. O((n log p)C) for some constant C.

• Use Coppersmith’s algorithm to compute loggh = logg0h0.

In other words we are saying that changing the presentation of the finite field does not slow down significantly the computation of discrete logarithm thanks to Lenstra’s algorithm [Len] that computes isomorphisms between finite fields in poly-nomial time.

4.2. Factor base phase. Once the presentation is found, one sets n1 to be

the smallest p-th power no less than n13(log p) 1

3(log n)− 1

3, n₂ equal to dn

n1e and

set the smoothness bound B = n

1 3(log n)23

(log p)23

, so that the the factor base is the set of (classes of) irreducible polynomials of degree ≤ B . Set λ equal the number in [1, p) such that n1= n

1

3λ and also define m = dλe. Set ν0(X) = Xn1n2−nν(X) so

that Xn1n2_{≡ ν}0 _{(mod µ) and deg ν}0_{≤ n}12.

For any (m + 1)-uple a0, . . . , am ∈ Fp[X] of random polynomials of degree

bounded by 4B/λ one considers

Pa0,...,am(X) = a0(X) + X n2_a 1(X) + . . . Xmn2am(X) Qa0,...,am(X) = a0(X n1_{) + ν}0_(X)a 1(Xn1) + . . . ν0(Xm)am(Xn1)

so that, since n1 is a p-th power and powering by n1is a linear operation, and one

easily gets (Pa0,...,am)

n3 _{≡ Q}

a0,...,am (mod µ). Notice that

deg Pa0,...,am ≤ dλe

& n23(log n) 1 3 (log p)13λ ' +n 1 3 λ ≤ 3n 2 3_{(log n)}13_{(log p)}−13

(15)

deg Qa0,...,am ≤ dλen 1 2 + n₁4B λ ≤ 5n 2 3(log n) 1 3(log p)− 1 3.

If both Pa0,...,am and Qa0,...,am are B−smooth one obtains a multiplicative relation

among the elements of the factor base, i.e if we call h1, . . . hT the elements of the

factor base, we find a relation of the form

aj₁log_gh1+ · · · + aTj logghT ≡ 0 (mod pn− 1)

valid for any generator g of (Fp[X]/µ(X))∗. After collecting enough relations it

is likely that the system of equations found has rank T − 1 modulo every prime dividing pn− 1, so that one can compute a generator ˜g =QT

i=1h bi

i and find log˜ghi

To estimate the running time of this phase we assume that Pa0,...,am and

Qa0,...,am behave like random independent polynomials of degree respectively less

than 3n23(log n) 1 3(log p)− 1 3, 5n 2 3(log n) 1 3(log p)− 1

3, even if, as a₀, . . . , a_m vary, the

couples (Pa0,...,am, Qa0,...,am) do not cover the set of couple of polynomials with

that bound on the degree. With this hypothesis we can apply proposition 1 and deduce that the average number of (m+1)-uples (a0, . . . , am) that need to be tested

before finding a multiplicative relation is P_Fp 3n23_{, B} −1 · P_Fp 2n23_{, B} −1 ∈ Lpn 1 3, 8 3 .

Since the cardinality T of factor base can be estimated by a function in Lpn[1₃, 1]

(T is contained in the interval (pB−log2pB/2

B ,

pB

B)), the number of (m + 1)-uple

needed to be tried in order to find O(T ) different relation is bounded by a func-tion in Lpn[1₃,11₃] (notice that we have enough tuples). Computing and factoring

Pa0,...,am, Qa0,...,amtakes polynomial time, thus collecting all the relations requires a

number of operations estimated by a function in Lpn[1

3, 11

3]. Then the linear system

can be solved in O((T log pn)3) operations, estimated by a function in Lpn[1

3, 3].

In conclusion, with the assumption of “randomness” of Pa0,...,am, Qa0,...,am, the

complexity of this phase is estimated by a function in Lpn[1

3]

4.3. Individual logarithm phase and descent procedure. The idea to speed up the individual logarithm phase is the same of the factor base: if we want to compute the discrete logarithm of (the class) of a polynomial of degree signifi-cantly smaller than n, then it is better to consider polynomials of degree also smaller than n. The key ingredient is a descent procedure that expresses (the class of) a polynomial of degree d as a multiplicative combination of at most 2n polynomial of degree ≤√dB, where B is the smoothness bound established during the previous phase.

Let us firstly see if one knows a procedure like this that runs in time estimated by a function in Lpn[1

3] and has already completed the factor base phase, then can

discrete logarithm of any element of the field in time estimated by another function in Lpn[1

3]. Let us suppose we want to compute the discrete logarithm of the class

of a polynomial h with respect to the class of another polynomial g and that we have completed the factor base phase finding another generator of the multiplicative group ˜g of low degree.

Applying the descent procedure on g we write g as a multiplicative combination of at most 2n polynomials of degree ≤ √nB; applying the descent procedure on

(16)

4. THE FUNCTION FIELD SIEVE 15

these polynomials we write g as a multiplicative combination of at most 4n2 poly-nomials of degree ≤ n14(B

2)

3

4; applying inductively the descent procedure less than

2 · (2n)t_{-times we find polynomials g}

i’s of degree ≤ n2

−t

b1−2−t_{, a}

i’s integer numbers

and a natural number k0≤ (2n)tsuch that g =Q k0

i=1g ai

i . Choosing t = log2n then

all the gi’s have degree ≤ B, allowing to write g as a product of elements in the

factor base and to find lh∈ Z such that h = ˜glh.

Doing the same with g instead of h one finds lg∈ Z such that g = ˜glg, and one

can easily compute

loggh = lhl−1g (mod pn− 1).

Let us take a function φ ∈ Lpn[1

3] estimating the average running time of the

de-scent procedure: since this procedure has been applied at most O (2n)log2n, then

the process just described can be performed in at most φ · exp C log n2_{for some C,}

and this quantity is dominated by φ0(pn) for some φ0(x) ∈ Lx[1₃].

Let us now describe the descent procedure. Suppose we are given a polynomial G(X) of degree d > B. Let n3 be the smallest p-th power no less than pn_d and

n4 = d_nn

3e, so that X

n3n4 _{≡ ν}0_{(X) (mod µ)(X) for a polynomial ν}0 _{of degree at}

most 2n23; let moreover n₃ = pn

dλ

0 _{for some λ}0 _{∈ [1, p) and let m = dλ}0_{e. For}

any (m + 1)-uple a0, . . . , am∈ Fp[X] of polynomials of degree bounded by _λd0 let us

define

Pa00,...,am(X) = a0(X) + X

n4_a

1(X) + . . . Xmn4am(X)

Q0_a₀_,...,a_m(X) = a0(Xn3) + ν0(X)a1(Xn3) + . . . ν0(Xm)am(Xn3)

Since n3 is a p-th power, powering by n3 is a linear operation and one easily gets

(P_a0

0,...,am)

n3_{≡ Q}0

a0,...,am (mod µ)

Moreover if am6= 0 then deg Pa00,...,am ≥

√ nd and in general deg P_a0 0,...,am≤ dλ 0_ed √ nd λ0 e + d λ0 ≤ 3 √ nd deg Q0_a₀_,...,a_m≤ dλ0en23 _{+ n}₃d λ0 ≤ 2 √ nd.

The strategy is to consider all the (m+1)-uple a0, . . . , amsuch that P0(X)a0,...,am is

divisible by G(X) and seek tu find a tuple such that both P_a0₀_,...,a_m/G and Q0_a,bare √

bd-smooth: once such pair is found, if we find irreducible factorization P_a,b0 /G = QnP 0 i=1f ai i and Q 0 a,b = QnQ0 i=1g bi

i and use the fact n1 is invertible (mod pn− 1) we

obtain that G ≡ nP 0 Y i=1 f−ai i · = n_Q0 Y i=1 g pn n1bi i (mod µ)

for nP0, n_Q0 < n and polynomials f_i’s g_i’s of degree ≤

√ bd.

How much time does this procedure take? Finding a basis of VG := {(a0, . . . , am) ∈

Fp[X]m+1: deg a0, . . . , deg am≤ _λb0, G|Pa00,...,am} is a matter of linear algebra in the

(17)

Finding a tuple (a0, . . . , am) ∈ VGsuch that Pa,b0 /G and Q0a,bare

√

Bd−smooth can be done by trials, i.e. taking random a0, . . . , am∈ VG, computing P00

a0,...,am≤/G

and Q0

0

a0,...,am≤ and checking whether they are

√

Bd-smooth and repeating this procedure until one gets a positive answer. If we treat Pa00,...,am/G and Q

0

a0,...,am as

“random”, i.e. if we assume that the probability of Pa00,...,am being

√

Bd-smooth is equal to P_F_p(3√nd,√Bd) and that this event is independent of the event “Qa0,...,am

is smooth” having probability P_F_p(2√nd,√Bd), then the average number of (m+1)-uples in VG we have to try before we find one yielding a relation is less than

P_F_p3 √ nd, √ Bd −1 · P_F_p2, √ Bd −1 ∈ Lpn 1 3, 5 2 .

Since computing and factoring P_a0₀_,...,a_m and Q_a0₀_,...,a_m can be done in O((log p)3_n3₎

(since all polynomials have degree ≤ 2n), we conclude that the average running time of the descent procedure is dominated by a function in Lpn[1₃,5₂].

(18)

CHAPTER 2

Recent progress

In 2013 Antoine Joux pulished a new index calculus algorithm for the DLP of complexity in Lpn[1

4] on finite fields of “small” characteristicv[Jou]. Basically with

the same ideas in 2014 he was able, together with Barbulescu, Gaudry, Joux and Thom´e to improve significantly this complexity: in [BGJT] is presented an algo-rithm that, under specific heuristic assumptions, runs in time exp{O(log log pn)2} = (log pn₎O(log log pn)_.

In general we say that an algorithm has quasi-polynomial complexity if there exists a polynomial p such that the algorithm, given an input of length N , runs in a time less than exp{O ((log N )c_{)} for some constant c > 0.}

1. The basic ideas

The algorithm in [Jou] falls in the class of algorithms described in [JL], where it is presented a generalization of Coppersmith’s ideas that leads to sub-exponential algorithms even without exploiting the linearity of Frobenius morphism, but con-structing multiplicative relations between polynomials of small degree. In particular choosing in the right way the parameters in [JL] it is possible to define the algo-rithm in [Jou] (and this is the way Joux himself describe his algoalgo-rithm) but in my opinion the ideas behind Joux’s new index calculus are clearer if we forget the two-variables-setting in [JL] and work over a polynomial ring in one variable and keep in mind the “standard” index calculus or Coppersmith’s improvement.

Suppose we want to compute the discrete logarithm on a finite field of small characteristic K; a first observation is that, differently from what we have done in the previous chapter, we can also present the field K as a (“high” degree) ex-tension of a non-prime field. Already in the case of “medium” characteristic Joux and Lercier shown as this could be convenient, so let us say we present the field K as FQ[X]/µ(X) for some field of cardinality Q and some irreducible polynomial

µ ∈ FQ. We later determine how to choose Q with respect to #K

One of the ideas in [Jou] is similar to a technique described by Coppersmith and contained in [BFMV]: in this article is described the use of Adleman’s index calcu-lus on F2127and the authors notice that a model of this field is F2[X]/(X127+X +1);

in particular if we call x the class of X in the quotient, then for any polynomial P one has that P (x)128= P (x128) = P (x2+ x), and during the factor base phase this observation gives a lot of relations simply by taking P of degree less than a half of the smoothness bound. In this example we see that when computing the discrete logarithm on a finite field of characteristic p , if one finds a p-th power q (not necessarily equal to p or to Q) and a special generator of the extension L/FQ

on which the q-Frobenius acts in some “simple” way, then can take advantage of the linearity of the q-Frobenius. In the example we have seen the authors found a

(19)

18 2. RECENT PROGRESS

generator of the extension x such that x128 = x2+ x, in general it can be useful to find a generator x of the extension such that xq is equal to a rational function of small degree computed in x. In other words we want two polynomials h0, h1 of

“small” degree such that µ(x) divides h1(x)xq− h0(x).

Another technique recalls what Coppersmith calls systematic equations. The relations needed in the factor base phase are essentially given by congruences a(X) ≡ b(X) (mod µ(X)) between smooth a, b ∈ FQ[X]; half of the job can

be made taking a(X) varying in some family of polynomials that somehow are smooth apriori. This is possible for example by choosing a fixed polynomial F that factors into linear polynomials over FQ and then, for every α of small degree,

taking a(X) = F (α(X)) and b(X) equal to the polynomial of smaller degree in F (α(X)) + (µ(X)). By the previous discussion it would be natural to ask that FQ

contains a subfield of order q (say Fq) and choose F (T ) = Tq− T .

A third ingredient in Joux’s index calculus algorithm is to “amplify a relation using homographies”. In fact he considers the usual action of PGL2(FQ) on FQ[X],

defined in the following way: a b c d , f (X) −→ f a bc d (cx + d)deg ff ax + b cx + d .

Then he observes that if a polynomial F is used to find “systematic equations” then all the conjugate of F under the action of PGL2(FQ) can also be used to find

“systematic equations”, since they are completely factored: this allows to find many other equations. We notice that F (X) = Xq− X is already PGL2(Fq)-invariant

and thus if we want to really “amplify” this relation it is necessary that FQ is a

proper extension of Fq.

2. The first quasi-polynomial algorithm

As already said, the ideas explained above were the basis for an algorithm of complexity in L[1₄, c], but we do not describe it and instead look at the quasi-polynomial algorithm in [BGJT].

2.1. The presentation of the field. The ideas in the previous section cannot be applied on any finite field, but only on fields having a sparse medium subfield representation:

Definition. A finite field K admits a sparse medium subfield representation if

• K contains two subfields Fq ⊂ FQ of order respectively q, Q = q2

• there exist an irreducible polynomial µ ∈ FQ[X] and a two polynomials

h0, h1∈ FQ[X] of degree less than log log ([K : FQ]) + 2 (i.e. h0, h1 have

small degree) such that

µ(X)|h1(X)Xq− h0(X) and FQ[X]/µ(X) ∼= K.

Moreover a sparse medium subfield representation of K is the datum of (q, µ, h0, h1)

(20)

2. THE FIRST QUASI-POLYNOMIAL ALGORITHM 19

We notice that if K has a sparse medium subfield representation (q, µ, h0, h1)

then [K : Fq] ≤ 4q; moreover the algorithm reach optimal complexity in the case

where [K : FQ] is “near” to q. If we wanted to face the DLP on a field K that

does not contain a subfield of the right size (for example a field of size 2l_{for a large}

prime l) then we should embed K in a slightly larger field K0: suppose that K has order pk _{for some prime p and some integer k > p, defined k}0 _{to be d}1

2logpke we

can choose K0 to be a field of order pk0k _{with q = p}k0_{. There is no proof that any}

field having a subfield of the right size admits a sparse medium representation, nei-ther nei-there is a proof that the K0 built in this way admits a sparse medium subfield representation; however in [Jou] Joux has collected experimental evidence that a field of characteristic 2 and order q2k _{for k ≤ q admits a sparse medium subfield}

representation (q, µ, h0, h1) for some polynomials h0, h1 of degree less than 2.

Another observation is that the algorithm would work also if in the definition above we had written Q = qk00 _{for some k}00 _{different from 2 but still “small” if compared}

to q.

From now on we denote by K having a fixed sparse medium subfield representation (q, µ, h0, h1) and we denote by Fq, FQ the two subfields of K of order respectively

q, Q = q2_{; we also use k for the degree [K : F}Q] (thus #K = q2n) and δ for

max{deg h0, h1}. Moreover we need a notation for the action of the Frobenius on

the polynomial ring FQ[X]: given f (X) = adXd+ · · · + a0 ∈ FQ[X] we denote

by fφ_{(X) the polynomial a}

dXd+ aq0; in other words fφ is the unique polynomial

satisfying (f (X))q = fφ_(Xq_).

2.2. The descent procedure. The difference between [Jou] and [BGJT], is mainly in the smoothing procedure necessary in the individual logarithm phase, and here we analyze the sub-algorithm of the quasi-polynomial algorithm in [BGJT] used as a “smoothing procedure” i.e. a procedure that, given a polynomial f of degree d > 1, expresses the discrete logarithm of [f ] = f + (µ) as a linear combination of the discrete logarithms of (classes of) polynomial of degree ≤ d₂.

The procedure relies on the following observation: given m = a b

c d ∈ GL2(FQ)

and f (X) ∈ FQ[X] of degree d and monic, for simplicity, we can substitute U =

af + b and V = cf + d in the identity Uq_{V − U V}q_{= V} Q

(21)

that h1(X)Xq ≡ h0(X) (mod µ(X)), we obtain that

cmh1(X)d Y α ∈ P1(Fq) m−1α 6= ∞ f (X) − m−1α= h1(X)d(cf (X) + d) Y α∈Fq (a − αc)f (X) + (b − αd)= h1(X)d cf (X) + daqf (X)q+ bq− h1(X)d af (X) + bcqf (X)q+ dq= h1(X)d cf (X) + daqfφ(Xq) + bq− h1(X)d af (X) + bcqfφ(Xq) + dq≡ cf (X) + d aqh1(X)dfφ h0(X) h1(X) + bqh1(X)d − − (af (X) + b) cqh1(X)dfφ h0(X) h1(X) + dqh1(X)d (mod µ(X)) where cm∈ F∗Q is easy to compute from m, and m

−1_{α =} αd−b

αc−a, including the limit

cases like α = ∞. Notice that h1(X)dfφ _h 0(X) h1(X)

is a polynomial of degree ≤ δd and thus if we define

G(m, f ) =(cf (X) + d) aqh1(X)dfφ h0(X) h1(X) + bqh1(X)d − − (af (X) + b) cqh1(X)dfφ h0(X) h1(X) + dqh1(X)d

then we have that deg G(m, f ) ≤ (δ + 1)d and we can sum up the arguments above as cmh1(X)d Y α ∈ P1(Fq) m−1_{α 6= ∞} f (X) − m−1α≡ G(m, f ) (mod µ(X)).

Anytime G(m, f ) is d₂_{-smooth (over F}Q) then the congruence above is

“inter-esting” because implies a relation if the form

q+ X i=1 log_g([f + ei]) = t X i=1

log_g([fi]) − d logg[cm] − d log[h1(X)]

for some ∈ {0, 1}, t ∈ Z>0, ei ∈ FQ and f1, . . . ft irreducible polynomial of degree

≤ d

2. If one finds “enough” m such that G(m, f ) is d

2-smooth, then all the relations

in the discrete logarithms collected can be seen as a linear system in the variables log_g_{([f + e]) for e ∈ F}Q and solved, reaching the desired result.

In particular it is important to know how many different congruence relations one obtains when m varies in GL2(FQ) and how many of them are interesting.

Firstly, up to multiplicative constants in F∗Qtwo matrices m, m0that are in the same

class of PGL2(FQ) give the same equation; it is also easy to check that the same

happens if the PGL2class of m0m−1is the class of an element in PGL2(Fq). Looking

at the left hand side of equation 2.2 we can convince of the following: two matrices m, m0give the same left hand side (up to constants) iff [m]−1P1(Fq) = [m0]−1P1(Fq)

and this happens iff [m]−1 _{= [m}0_]−1_{[n] for some n ∈ GL}

2(Fq) (here [m] denotes

(22)

congruence generated is the number of right cosets of PGL2(Fq) in PGL2(FQ), that

is

Q3_{− Q}

q3_{− q} = q 3_{+ q.}

We postpone the discussion about the number of interesting relations; for now we just hope that this number is at least q2(i.e. the number of variables) and that the linear system has a unique solution.

Before writing the algorithm let us make one last observation due to Cheng and others in [CWZ]: if f (X) is irreducible and divides to h1(X)Xq − h0(X) then

each time that the left hand side of 2.2 is multiple of f , then also the right hand size is multiple of f (this is because the congruence is actually (mod h1(X)Xq−

h0(X))), thus we never obtain an “interesting” relation involving f . This is why

such polynomials are called traps by Joux and Cheng and why it is better to avoid them in the descent algorithm, excluding those relations that contain traps in the right hand side.

In the following algorithm, instead of looking at the discrete logarithm in K∗ we look at the dicrete log in K∗_/F∗_q, denoted as log∗, both for simplicity and for efficiency reasons (the subalgorithm should be executed many times during a single execution of the algorithm).

BGJT sub-algorithm of descent. Given a sparse medium subfield repre-sentation (q, µ, h0, h1) of a field of order q2n and a polynomial f of degree d > 1

coprime to h1(X)Xq− h0(X), produces an array of integers (w1, . . . , wl) ∈ Zl and

an array of monic irreducible polynomials (f1, . . . fl) ∈ FQ[X]l such that every

component is co-prime to h1(X)Xq− h0(X) has degree ≤ d₂ and f ≡ CQ l r=1f

wr

r

(mod µ) for some C ∈ F∗Q

(1) (Preparation) If deg f = 1 output (f ), (1). Enumerate the elements e1, . . . , eQ = 0 of FQ and enumerate matrices m1, . . . , mq3+q ∈ GL2(FQ)

such that their classes form a complete system of representatives in PGL2(Fq)\PGL2(FQ).

For r = 1, . . . , Q s = 1, . . . , q2 set Msr= q

k₋₁

q−1δsr. Set i ← q

2_{, j ← 0.}

(2) (Collecting relation) Set j ← j + 1, write mj = a bc d, compute

G(m, f ) =(cf (X) + d) aqh1(X)dfφ h0(X) h1(X) + bqh1(X)d − − (af (X) + b) cqh1(X)dfφ h0(X) h1(X) + dqh1(X)d

and find the factorization into monic irreducible polynomials G(mj, f ) =

Cpu1

1 · · · p ut

t .

If for each r = 1, . . . , t pr has degree ≤ d₂ and does not divide

h1(X)Xq− h0(X) then set i ← i + 1, Fi← (p1, . . . , pt), Wi← (u1, . . . , ut)

and for each r = 1, . . . , Q set Mi,r← 0 if er∈ m/ −1j P1(Fq), set Mi,r← 1 if

er∈ m−1j P 1

(Fq). If j < q3+ q repeat this step, otherwise go to the next

step.

(3) (Linear algebra:) Find the row echelon form of the matrix M = (Msr)s≤i,r≤Q,

that is compute matrices A ∈ GLi(Z), N ∈ Zi×Qsuch that AM = N such

that N is in row echelon form.

Find the last nonzero row of N and let this row be the i0-th: if the pivot

(23)

output FAIL; otherwise w equal to the inverse of Ni0Q (mod

q2n₋₁

q−1 ) and

set vQ+1 ← Ai0,Q+1, . . . , vi ← Ai0,i (they are integer numbers s.t. such

that the last row of N is congruent to vQ+1MQ+1+ . . . viMi (mod q

2n₋₁

q−1 ),

where Msis the Ms-th row of M )

(4) (Conclusion:) Set F equal to the array of all the polynomials appearing in FQ+1⊕ · · · ⊕ Fi(without repetitions) and set W to be an array of the form

(0, . . . , 0) and length equal to length(F ). For r = 0, . . . , length(F ) find the couples of integers (i1, j1), . . . , (it, jt) such that Fi1(j1) = · · · = Fit(jt) =

F (r) and set W (r) = vi1Wi1(j1)+· · ·+vitWit(jt) (mod (q

n_{−1)/(q −1))q.}

Output F and W

¡Except from the factorization of polynomials, all the other procedures are deterministic and we can estimate the running time (we are not interesting in op-timizing it, just remark its polynomial nature): the first step takes O(Q3_{(log Q)}3₎

operations, mainy for computing the representatives mj’s, a single execution of the

second step (that is repeated q3_{+ q times) takes expetced time O(d}3_{Q) (mainly}

for the factorization), while the third step is standard linear algebra and can be performed in O((q3_{n log Q)}3_{) operations. Thus the expected running time of the}

descent step is O(q9n3(log q)3+ d3q5) and in the case d ≤ deg µ ≤ 2q, then this time is O(q9n3(log q)3).

The main problem is whether the algorithm fails or succeeds in his purpose and this entirely depends on the rank of the matrix (Msr); as in [BGJT] we can assume

that the failing is “improbable” looking at the following heuristics: • If G(m, f ) war always d

2-smooth the matrix (M r

s) would be invertible over

the integers.

• Of course G(m, f ) is not “random” but if we assume that the probability of G(m, f ) being d₂-smooth is equal to the probability of a random poly-nomial of degree ≤ (δ + 1)d, then, by theorem 2, the number of equation is at least (2C(δ + 1))−2δ−2q3_{> (log q)}−C0_{log log q}

q3_{for two constants C, C}0_.

Thus if we choose any > 0 then, for q big enough the number equation is > q3−_{, while the number of variables is q}2

• In [Jou] has been collected experimental evidence supporting this hypoth-esis in a field of characteristic 2.

2.3. The factor base phase. The elements of the factor base are the classes of monic polynomials of degree 1 together with the class of h1, thus it has size

Q = q2_{. As in the version of the function field sieve we have seen, in the first}

phase one does not compute the discrete logarithm of the elements in the factor base with respect to a fixed generator, but finds a generator among the elements if the factor base and then finds the discrete logarithm of all the other elements with respect to it. The strategy to collect multiplicative relations is the same used in the sub-algorithm we have already analyzed: for any matrix m ∈ GL2(FQ) one has

the congruence cmh1(X) Y α ∈ P1(Fq) m−1α 6= ∞ X − m−1α≡ G(m, X) (mod µ(X))

(24)

and anytime G(m, X) is completely factored m yields a relation. As before one only has to test the smoothness of G(m, X) for m in a complete set of representative of PGL2(Fq)PGL2(FQ) and after this has been done one tries to solve the linear

system.

As in the descent algorithm, there is no proof that the rann of the linear system is q2

, neither in special cases like in Kummer extension Fq2[X]/(Xq−1− α)

(see [CHZ]), but is an assumption necessary to the success of the algorithm and is supported by the same observations as before.

Now that we have described the factor base phase and a descent procedure we are ready to write down the algorithm described in [BGJT] working on a field having a fixed sparse medium subfield representation. We use arrays, denoted with the usual parenthesis, and given two arrays A, B we denote as A ⊕ B the array obtained by concatenating them; moreover we denote the empty array (i.e. the empty function) as ().

BGJT Algorithm for discrete logarithm. Given a sparse medium subfield representation (q, µ, h0, h1) of a field of order q2n and two polynomials h, g not

divisible by µ finds an integer n such that gn_{≡ h (mod µ)}

(1) Preparation: Enumerate the elements e1, . . . eQ = 0 of FQand find the

dis-crete logarithm of e1, . . . , eQ−1confronting them with g

q2n −1

q−1 , . . . , g(q−1) q2n −1

q−1 .

Enumerate matrices m1, . . . , mq3_+q ∈ GL₂(F_Q) such that their classes

form a complete system of representatives in PGL2(Fq)\PGL2(FQ). For

r = 1, . . . , Q s = 1, . . . , q2 set Msr = (q

2n₋₁₎

q−1 δsr. Set i ← q

2_{, j ← 0,}

G ← (g), H ← (h)

(2) Collecting relation for the factor base phase: Set j ← j + 1, write mj = a b

c d and compute

G(mj, X) = (cX + d) (aqh0(X) + bqh1(X)) − (aX + b) (cqh0(X) + dqh1(X)) .

If G(mj, X) is not 1-smooth and j < q3+q repeat this step, if G(mj, X) is

not 1-smooth and j = q3_{+ q go to the next step, otherwise continue. Set}

i = i + 1, find the irreducible factorization G(mj, X) = cQQ_r=1(X − er)lr

and for each r = 1, . . . , Q set Mir← lrif er∈ m/ j−1P1(Fq), set Mir← lr−1

if er∈ m−1j P1(Fq). If j < q3+ q repeat this step, otherwise go to the next

step.

(3) Linear algebra step: Find the Smith normal form of M = (Msr)s≤i,r≤Q,

i.e. compute matrices A ∈ GLi(Z), B ∈ GLQ(Z), D ∈ Zi×Q such that

M = ADB, Drs= 0 for r 6= s and Drrdivides Dr+1,r+1for r = 1, . . . Q −

1; moreover compute C = B−1. If Drr ∈ Z/ ∗ for each r = 1, . . . , q2− 1

return FAIL. Set g0 ← Q Q

r=1(X − er)BQr; for r = 1, . . . , Q set lr = CrQ (with this

assignment lr= log∗g0(X − er))

(4) Individual logarithm phase for h: Set ˜H ← (), ˜W ← () For r = 1, . . . , lenght(H) do the following: execute the sub-algorithm with the input H(r) and the presentation (q, µ, h0, h1) to produce the array of polynomials F and the

array of integers W1and set ˜W ← ˜W ⊕ W (r) · W1, ˜H ← H ⊕ F1.

Set H equal to the array of all the polynomials appearing in ˜H (with-out repetitions) and set W to be an array of the form (0, . . . , 0) and length equal to length(H). For r = 0, . . . , length(H) find the integers

(25)

s1 < . . . zst such that ˜H(s1) = · · · = ˜H(st) = H(r) and set W (r) =

˜

W (s1) + · · · + ˜W (st) (mod (q2n− 1)/(q − 1)).

If deg W (i) ≤ 1 for every r = 1, . . . , l repeat this step, otherwise go to the next step.

(5) Individual logarithm phase for g: Set ˜G ← (), ˜V ← () For r = 1, . . . , lenght(G) do the following: if deg G(r) = 1 set ˜G ← ˜G + (G(r)), ˜V ← ˜V + V (r), oth-erwise execute the sub-algorithm to produce the array of polynomials F1

and the array of integers W1and set ˜V ← ˜V ⊕ V (r) · V1, ˜G ← G ⊕ F1. Set

G equal to the array of all the polynomials appearing in ˜G (without rep-etitions) and set V to be an array of the form (0, . . . , 0) and length equal to length(G). For r = 0, . . . , length(G) find the integers s1 < · · · < st

such that ˜G(s1) = · · · = ˜G(st) = G(r) and set V (r) = ˜V (s1) + · · · + ˜V (st)

(mod (qn− 1)/(q − 1)).

If deg V (i) ≤ 1 for every r = 1, . . . , l repeat this step, otherwise go to the next step.

(6) Conclusion: For r = 1, . . . Q do the following: if there exists s such that G(s) = X − er then set nr = W (s), otherwise set nr = 0; if

there exists s such that H(s) = X − er then set mr = W (s),

other-wise set nr = 0. Set m = l1m1+ . . . lQmQ (mod (q2n− 1)/(q − 1)) and

n = l1n1 + . . . lQnQ (mod (q2n − 1)/(q − 1)). Compute n0 such that

nn0≡ 1 (mod (q2n− 1)/(q − 1)) and compute the element C ∈ F∗Q such

that h ∼= Cgn0m_{. Find log}

g([C]) (this can be done simply by confronting

C with gq2n −1q−1 _{, . . . , g}(q−1) q2n −1

q−1 _{) and output n}

0m + logg([C]).

The algorithm above may fail mainly for two reasons: either because the fac-tor base phase fails (maybe the classes of the linear polynomials do not generate the multiplicative group or maybe the equations found are not enough) or because the sub-algorithm fails. However the proof of the correctness of the algorithm is essentially contained in the congruence relation 2.2. At the end of step 2 the matrix M describes a set of equations for the log([X − er])’s, in the sense that

PQ

r=1Msrlog∗([X − er]) = 0 for each s = 1, . . . , i. If the matrix M has rank Q − 1

modulo every prime dividing (q2n − 1)/(q − 1) then the matrix D in the Smith normal form is diagonal with elements 1, . . . , 1, (q2n− 1)/(q − 1), the system of equations given by M is equivalent to the system of equations given by the first Q − 1 rows of B and if we set g0 ← Q

Q

r=1(X − er)BQr, then by standard linear

algebra one can prove that lr= log∗g0(X − er).

Knowing the sub-algorithm then it is obvious that at the end of each execution of step f the arrays H, W satisfie h ≡Q_H(r)˜ W (r)˜ _≡_{Q H(r)}W (r)_{; the analogous}

holds for the next step. Given what we have said n = log∗_g₀g, m = log∗_g₀h and the correctness of the algorithm follows.

Let us now estimate the running time of this algorithm. The first three steps are similar to a singular execution of the sub algorithm, thus they are not a bot-tleneck, since the sub-algorithm should be executed at least once during the fourth and fifth steps. Since also the last step is negligible, to understand the running time of this algorithm it is enough to estimates the time spent executing the fourth step (the fifth is similar). The fourth step consists in a “for” cycle and a second part needed to write the data collected during the “for” cycle in a more efficient

(26)

way; since the for cycle is more time-consuming we can ignore the second part for the analysis of the running time; moreover during the execution of the for cycle most of the time is spent executing the sub-algorithm, thus the running time of the algorithm is dominated by the time spent executing the sub-algorithm multiplied by a constant.

We are left to estimate how many times the sub-algorithm is executed during the various executions of step 4 (the same estimate holds for step 5 too). Let Nhbe the

number of times step 4 is executed and for r = 1, . . . , Nglet Hrbe the array named

H as it is at the end of the r-th execution of the fourth step; let moreover H0= (h).

Let Lrbe the length of Hr, let drbe the sum of the degree of the polynomials in Hr.

The algorithm is designed so that each coordinate of Hris a polynomial of degree

≤ max{1, 2−r_{deg h}, and this implies that N}

g ≤ log2(deg h). We can also prove

that for each r = 1, . . . , Ng, one has dr≤ (δ+1)(q3+q)dr−1≤ (δ+1)r(q3+q)rdeg h;

to prove the inductive inequality let us recall the set of the coordinates of Hr is

the union, for every p coordinate of Hr−1, of the polynomials in the output of the

sub-algorithm when it is given p as an input. By the property of the sub- algorithm one has that

dr≤ Lr−1

X

s=1

X

{deg P : Pin the output of the sub-algorithm when the input isHr−1(s)}

≤

Lr−1

X

s=1

(δ + 1)(q3+ q)dr−1(δ + 1)(q3+ q)Hr−1(s) ≤ (δ + 1)(q3+ q)dr−1.

Since during the r-th execution of the fourth step the sub-algorithm is executed Lr ≤ dr times we deduce that the number of times the sub-algorithm is executed

during the various executions of step 4 is

Nh X r=1 Lr≤ Nh X r=1 dr≤ Nh X r=1 (δ + 1)r(q3+ q)rdeg h ≤ 2(δ + 1)Nh_(q3_{+ q)}Nh_{deg h ≤}

≤ 2(δ + 1)log2(deg h)_(q3_{+ q)}log2(deg h)_{deg h ≤ 4n(qδ)}3 log2n_.

Since the execution of the sub-algorithm needs Oq9n3(log q)3 operations, the whole algorithm has complexity On4_{(log q)}3_q12_(qδ)3 log₂n_{. Since δ < log log q}

and in any case n < 4q we can say that for every > 0, the algorithm has complexity Oq(3+) log2n

.

Depending on the relation between n and q this estimate can lead to exponential, sub-exponential quasi-polynomial algorithm, or maybe an intermediate running time. If we consider only the fields K of order q2n _{for 10}4_{n > q (of course 10}3 _can

be replaced by any constant) admitting a sparse medium subfield representation (q, . . . ), then for this family of fields Joux’s algorithm is quasi polynomial since one deduce that q < 104_{log q}n_{, n < log q}n_{and thus q}(3+) log₂n_{= O(exp{5(log log q}n₎2_})

(27)

3. A rigorous quasi-polynomial algorithm

The same basic ideas we have seen at the the beginning of this chapter, have been exploited by Granger, Kleinjung and Zumbragel in [ZKG] to produce a prob-abilistic algorithm whose expected runnning time can be rigorously proved to be quasi-polynomial.

This algorithm requires a sparse medium subfield representation of the target finite field, but with one more hypothesis than the one needed by the BGJT algo-rithm and moreover required the “medium subfield” to be bigger so that the effect of “amplification of a relation” is bigger

Definition. A strictly sparse medium subfield representation of a field K is a 5-uple (q, FQ, µ(X), h0(X), h1(X)) where q is a prime power, FQ is a finite field

containing of order Q = qk

, µ ∈ FQ[X] is an irreducible polynomial, h0, h1∈ FQX

are polynomial of degree at most 2 such that

µ(X)|h1(X)Xq− h0(X) and FQ[X]/µ(X) ∼= K.

The GKZ algorithm can be applied only on fields K admitting a strictly sparse medium representation and is proven to be correct and quasi-polynomial for all fields such that Q ≥ q18; as previously seen changing the representation takes polynomial time by [Len].

The key ingredient of ZKG algorithm is a probabilistic polynomial time de-scent procedure that allows to express a the discrete logarithm of an irreducible polynomial of degree 2d in terms of irreducible polynomials of degree dividing d.

Actually the procedure cannot be applied to all the polynomials of even degree, because of the presence of “traps”, as in BGJT algorithm, thus to describe precisely the descent procedure we need the following

Definition. Given a strictly sparse medium subfield representation (q, FQ, µ(X), h1(X), h1(X)) of a field, we say that an element α in an algebraic

closure of FQ such that [FQ(α) : FQ] = 2d is a trap if either h1(α)αq− h0(α) = 0

or h1(α)αqQ

d

− h0(α) = 0 or h1(α) = 0 or h0(α)/h1(α) ∈ FQd where F_Qd is the

subfield of FQ(α)having cardinality Qd.

If an element α of an algebraic closure of FQ is not a trap is said to be good

and a polynomial in FQ[X] is a good polynomial if all its roots are good.

Notice that given a field FQd0 of cardinality Qd 0

extending FQ, the number of

traps is at most Qd02 log

2d0+ 4Q

d0

2q: if d0is odd it is sufficient to count the elements

that does not generate FQd0, thus it is sufficient the term Q d0

2 log₂d0, otherwise one

must add the roots of h1(α)αqQ

d

− h0(α) = 0 (their number is at most Q

d0 2q + 2),

the roots of h1(α)αq−h0(α) = 0 (their number is at most q +2) and all the elements

such that h0(α)

h1(α) ∈ F_Qd02 or h1(α) = 0 (their numbers is at most 2Q d0

2 + 2); the sum

of all these terms is less than Qd02 log

2d0+ 4Q

d0 2q.

We can now describe precisely how the descent works:

Proposition 2 (Descent proposition). There exists an algorithm running in expected time O(q6k4d4(log q)3) takes as input a strictly sparse medium subfield representation (q, FQ, µ(X), h1(X), h1(X)) of a field K ∼= FQ[X]/µ(X) such that

Discrete logarithm over finite fields of "small" characteristic

Facolt`

a di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea Magistrale in Matematica

Tesi di Laurea

Discrete logarithm in finite fields

of small characteristic

Candidato

Relatore

Correlatore

Guido Maria Lido

Prof. Ren´

e Schoof

Prof. Roberto Dvornicich

Contents

Introduction

Index calculus algorithms

Recent progress