# Improvements on the Discrete Logarithm Problem in GF(p)

Razvan Barbulescu

<figure><img src="image_1.png" /></figure>

## To cite this version:

Razvan Barbulescu. Improvements on the Discrete Logarithm Problem in GF(p). Cryptography and Security [cs.CR]. 2011. inria-00588713v3

HAL Id: inria-00588713

https://inria.hal.science/inria-00588713v3

Submitted on 14 Mar 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Improvements to the
Discrete Logarithm Problem
in $F_p^*$

Auteur:
Răzvan BĂRBULESCU

Directeur:
Pierrick GAUDRY

4 mars 2011

<figure><img src="image_3.png" /></figure>

Laboratoire Lorrain de Recherche en Informatique et ses Applications
<figure><img src="image_4.png" /></figure>
# Contents

<table><tr><td>1</td><td>Introduction</td><td>1</td></tr><tr><td>2</td><td>State of Art</td><td>3</td></tr><tr><td>2.1</td><td>Index Calculus</td><td>3</td></tr><tr><td>2.2</td><td>Smoothness</td><td>4</td></tr><tr><td>2.3</td><td>Sparse Systems</td><td>5</td></tr><tr><td>2.4</td><td>Complexity Analysis</td><td>5</td></tr><tr><td>2.5</td><td>Sieving</td><td>6</td></tr><tr><td>2.6</td><td>Double smoothness</td><td>7</td></tr><tr><td>2.7</td><td>Number Fields</td><td>9</td></tr><tr><td>2.8</td><td>Virtual Logarithms</td><td>11</td></tr><tr><td>2.8.1</td><td>Preparation</td><td>11</td></tr><tr><td>2.8.2</td><td>Schirokauer's maps</td><td>13</td></tr><tr><td>2.8.3</td><td>Definition of the virtual logs</td><td>15</td></tr><tr><td>2.9</td><td>Factorization Factory</td><td>17</td></tr><tr><td>2.10</td><td>Descent by Special Q</td><td>19</td></tr><tr><td>3</td><td>New Algorithm: Discrete Logarithm Factory</td><td>20</td></tr><tr><td>3.1</td><td>The algorithm</td><td>20</td></tr><tr><td>3.2</td><td>Admissibility</td><td>21</td></tr><tr><td>3.2.1</td><td>The early abort selection method</td><td>21</td></tr><tr><td>3.2.2</td><td>Early abort strategy</td><td>25</td></tr><tr><td>3.3</td><td>Complexity Analysis of the Discrete Logarithm Factory</td><td>31</td></tr><tr><td>3.3.1</td><td>Smoothing</td><td>31</td></tr><tr><td>3.3.2</td><td>Descent</td><td>32</td></tr><tr><td>4</td><td>Conclusion and Perspectives</td><td>37</td></tr></table>
<figure><img src="image_5.png" /></figure>
# Chapter 1

## Introduction

For long, number theorists have been puzzled by the equation $T^x \equiv S \mod p$. One calls $x$ the index or the discrete logarithm of $S$ in base $T$, and computing the index is called discrete logarithm problem, or DLP in short. Bouniakowsky [Bou70] gave the first algorithmic solution in 1870 and half a century later Kraitchik [Kra22] created the first sub-exponential method. Nevertheless, Kraitchik's work was forgotten and in 1971 Shanks gave a new solution called Baby-Step-Giant-Step with poorer performance: $O(p^{1/2})$. In the 70s everything made computer scientists believe that the DLP was a difficult problem<fnref n="1" />. Thus in 1976 Diffie and Hellman used exponentiation in $(\mathbb{Z}/p\mathbb{Z})^*$ as a potential one-way function and thanks to this example showed that the public key cryptography is feasible. Later came DSS and ECC which rely on the difficulty of DLP in $\mathbb{F}_{p^n}$ and on the elliptic curves, respectively.

In what follows we consider exclusively the case of $\mathbb{F}_p^*$ since a couple of issues make it the most important case for DLP. First, Bach [Bac84] proved that the DLP in $(\mathbb{Z}/NZ)^*$ is equivalent, by polynomial-time reductions, to the pair of problems (factorize $N$ and solve discrete logarithm for all prime factors $p$ of $N$); moreover the Silver-Pohlig-Hellman algorithm [PH78] makes reduction from $(\mathbb{Z}/NZ)^*$ to $\mathbb{F}_p^*$ effective. Next, every time a fast algorithm was designed for $\mathbb{F}_p^*$, it was adapted to the case $(\mathbb{F}_{p^n})^*$ with no loss of speed. Even though the converse is not true since Coppersmith designed an algorithm for $(\mathbb{F}_{2^n})^*$ faster than those for $\mathbb{F}_p^*$, one continues to use the case of prime fields as a starting point for the case of the most difficult finite fields, i.e. when $\log(p)$ is large compared to $n$. Finally, in the case of the elliptic curves no sub-exponential general purpose attack was published in the 25 years since ECC was created, but all the attempts try to replicate Index Calculus.

<footnote n="1">¹Diffie and Hellman write in [DH76] “However we assume that the best known algorithm for computing logs mod $q$ [i.e. Giant-Step-Baby-Step] is in fact close to optimal and hence $q^{1/2}$ is a good measure of the problem’s complexity, for properly chosen $q$”.</footnote>
Contrary to the case of factorization in which the input is a composite number $N$, in the case of DLP we are given a prime number $p$, a generator $T$ of $\mathbb{F}_p^*$ and an element $S$ of $\mathbb{F}_p^*$. Therefore the DLP based cryptosystems fix $p$ and $T$ and leave to $S$ the role of secret piece of information. But in 2003 Joux and Lercier [JL03] implemented an algorithm which significantly speeds up the computations if $p$ is known in advance. The algorithms which followed have two parts: one which depends only on $p$ called precomputations and one which depends on $T$ and $S$ called individual logarithm. Notice that this structure of algorithms is also useful in a number theoretical context where one might want to compute the discrete logarithm for a unique $p$ and a set of values of $S$. In 2006 Commeine and Semaev [CS06] published an algorithm with complexity $L_p(\frac{1}{3}, 1.902)$ for the precomputations and $L_p(\frac{1}{3}, 1.442)$ for the individual logarithm. Remember the traditional notation:

$$L_x(s, c) = \exp(c(\log x)^s(\log \log x)^{1-s})$$

where $\log$ denotes the natural logarithm. Sometimes we drop $x$ and/or the second constant and write $L(s)$ or $L_x(s)$. When speaking about algorithmic complexity we write $L_x(s, c)$ instead of $L_x(s, c)^{1+o(1)}$.

In this paper we improve Commeine and Semaev's algorithm in two ways. First we show a method to speed up the precomputations to $L_p(\frac{1}{3}, 1.639)$ using an idea of Coppersmith [Cop93] called Factorization Factory. For now, this algorithm is of theoretical interest only because, for computing DLP for values of $p$ in the range $p_0 < p < p_0 \cdot L_{p_0}(\frac{2}{3}, 0.905)$, it requires a permanent storage space of size $L_{p_0}(\frac{1}{3}, 1.639)$ computed in time $L_{p_0}(\frac{1}{3}, 2.007)$. Later we present a way to speed up the individual logarithm to $L_p(\frac{1}{3}, 1.232)$. This idea works as well in theory as in practice and is inspired from a paper of Pomerance [Pom82].

The second chapter is a short overview of many algorithms related to factorization and DLP. This can be used both as a general introduction to the field or to the state-of-art algorithms for DLP in particular. See the graph at the end of the report for the relations between different algorithms. In the third chapter we give full details for the individual logarithm. In particular we explain the early abort strategy and prove two theorems of analytic number theory.
# Chapter 2

## State of Art

### 2.1 Index Calculus

The main idea of all the sub-exponential algorithms for discrete logarithm is as follows: start by collecting linear relations between discrete logarithms of several elements, next solve the linear system obtained and finally express the discrete logarithm of $S$ in terms of the computed discrete logs. Discovered for the first time in 1922 by Kraitchik [Kra22], the idea was rediscovered in connection with the Diffie-Hellman cryptosystem in 1977 [Poh77],[Adl08]. A key notion for the algorithm is smoothness.

**Definition 1** Let $\mathcal{P}$ be a set of prime numbers that we call factor base. An integer $n$ is $\mathcal{P}$-smooth if all the prime factors of $n$ are in $\mathcal{P}$. If $\mathcal{P}$ is the set of prime numbers less than a bound $B$ then we say $n$ is $B$-smooth.

The shape of the algorithm below deserves particular attention because many recent algorithms speeded up each step of Index Calculus rather than changing the big lines. We call $p_i$ the $i^{th}$ prime number.

**Algorithm 1 Index Calculus**

INPUT: $T, S \in \mathbb{F}_p^*$ such that $T$ spans $\mathbb{F}_p^*$; a prime factor $q$ of $p-1$.

OUTPUT: $\log_T S$ modulo $q$.

0. Set $B \leftarrow [L_p(\frac{1}{2}, \frac{1}{\sqrt{2}})]$, $R \leftarrow \pi(B)$;

1. Choose and check random $h$ until $R$ values of $h$ are found such that $\text{Remainder}(T^h, p)$ is $B$-smooth; write each equation of type $T^h \mod p = p_1^{e_1} \dots p_R^{e_R}$ in additive form:

$$h = e_1 \log_T(p_1) + \dots + e_R \log_T(p_R) \mod q; \quad (2.1)$$
2. Solve the sparse linear system of size $R \times R$ with solution $\{\log_T l \mod q \mid \text{where } l \le B \text{ is prime}\}$;

3. Choose and check random h until one value is found such that Remainder($T^h S, p$) is B-smooth; this gives a relation of the form:

$$T^h S \mod p = p_1^{f_1} \dots p_R^{f_R}; \qquad (2.2)$$

4. Output $x = (f_1 \log_T p_1 + \dots + f_R \log_T p_R - h) \mod q$.

Notice that the input and the output are not the most general possible. Indeed, one can ask for $\log_T S \mod (p-1)$ with $S \in \langle T \rangle \neq \mathbb{F}_p^*$. It is solved by doing as follows: factor $p-1$; find a generator $\rho$ of $\mathbb{F}_p^*$; compute $\log_\rho T$ and $\log_\rho S$ for each prime factor $q$ of $p-1$; compute by the Chinese Remainder Theorem an $l$ such that $l \equiv \frac{\log_\rho S}{\log_\rho T} \mod q$ for all $q$; output $l$. One finds $\rho$ by random picks since the are $\varphi(p-1)$ generators in $\mathbb{F}_p^*$ and a raw inequality is $\frac{\varphi(p-1)}{p-1} > \frac{1}{\log(p-1)+5}$. In practice we test the values 2, 3, ... in a row, which is justified by Shoup [Sho90] if the Extended Riemann Hypothesis is true. It also allows us to consider $T$ smooth in the sequel.

## 2.2 Smoothness

One can expect the smooth numbers to be rare. Still, they are many enough to be used in DLP algorithms and we can estimate their number. Let's denote $\psi(x, B)$ the number of integers smaller than $x$ which are B-smooth. The following theorem of Candfield, Erdös and Pomerance published in 1983 estimates $\psi(x, B)$.

**Theorem 1** Let $\epsilon$ be a positive constant. Then it holds:

$$\psi(x, B)/x = u^{-u(1+o(1))}$$

uniformly in the region $x \ge 10$ and $B \ge (\log x)^{1+\epsilon}$, where $u = \frac{\log x}{\log B}$ and the limit implicit in the $o(1)$ is for $u \to \infty$.

proof as theorem 3.1 in [CEP83].

**Corollary 1** Let $x = L_p(a, b)^{1+o(1)}$ and $B = L_p(c, d)^{1+o(1)}$ with $(c, d) < (a, b)$ in lexico-graphical order. Then $\frac{\psi(x, B)}{x} = L_p(a-c, (a-c)\frac{b}{d})^{-1+o(1)}$.

Smoothness would not be such an interesting property without an efficient way to test it. The best algorithm for this purpose is the Elliptic Curves Method, abbreviated *ECM*. Indeed, let's call $x$ the number to test and $B$ the smoothness bound. Let's call an *ECM* run to launch *ECM* on as many curves as we can in
time $L_B(\frac{1}{2}, \sqrt{2}) \cdot (\log x)^{O(1)}$. As explained by Lenstra in [Len87], the result can be either a proper factor of the number or "not smooth" which is correct with probability 1/2. If we find a factor we make a next run and continue until we find the answer "not smooth" or we find all the factors of $x$. Since the total number of factors of $x$ is less than $\log_2 x$, it doesn't count in L-notation. Therefore the total time of a smoothness test is $L_B(\frac{1}{2}, \sqrt{2}) \cdot (\log x)^{O(1)}$. In the case of NFS we have $B = L_p(c, d)^{1+o(1)}$ and the smoothness test takes time $L_p(\frac{c}{2}, \sqrt{2cd})^{1+o(1)}$.

## 2.3 Sparse Systems

Since one deals with large linear systems, even a minor speedup of the algorithms for solving linear systems has a significant asymptotic effect. The naive method, i.e. Gaussian elimination, has complexity $O(n^3)$ while the best algorithm for solving linear systems has a complexity of $O(n^w)$ with $w \approx 2.49$ (see [CW08]). Still, the system in Index Calculus is sparse, i.e. it cannot have more than $O(\log(p))$ nonzero entries per line. Indeed, the lines of the matrix in the linear system are the valuation vectors of numbers of size $p$ in a factor base. Since each prime is larger than 2, a number of size $p$ has at most $\log_2(p)$ prime divisors by counting multiplicities. Therefore, each line of the linear system has at most $O(\log(p))$ nonzero entries. Several algorithms like [Wie86] were designed to solve sparse systems in $O(n^2w)$ where $w$ is the weight, i.e. the number of nonzero entries per line. In the first approximation, for the algorithms evolved from Index Calculus, if the system solved has size $L_p(s, c) \times L_p(s, c)$ then the linear algebra costs $L_p(s, c)^{(1+o(1))^2} \cdot \log p = L_p(s, 2c)^{1+o(1)}$.

## 2.4 Complexity Analysis

Pomerance writes in [Pom08] that he created the Quadratic Sieve while looking at the complexity analysis of former algorithms and thinking about which step can go faster. In order to compute the complexity of Index Calculus we consider the following problem:

**Problem 1** Let $N \in \mathbb{N}$ be given. Assume one can use a generator of random numbers of size $L_N(\sigma, \gamma)$ with $\sigma \in (0, 1)$ and $\gamma > 0$ fixed. Assume also that one can inspect for smoothness in negligible time. Choose convenient parameters $s \in (0, 1)$ and $c > 0$ and design an algorithm which in optimal time finds $[L_N(s, c)]$ numbers $L_N(s, c)$-smooth and then solves a sparse linear system of size $L_N(s, c)$.

Index Calculus spends part of its time on solving problem 1 for $N = p$, $\sigma = 1$ and $\gamma = 1$ by a choose&check strategy. Indeed, step 1 solves the first part of
the problem because we find $\pi(L_p(s, c))$ relations with $\pi(x) = \#\{p \text{ prime } \le x\}$ and because according to the Prime Number Theorem $\pi(x) \sim \frac{x}{\log x}$ which is $x$ in $L$ notation. Next, step 2 solves a sparse linear system of size $\pi(L_p(s, c)) = L_p(s, c)^{1+o(1)}$.

The time needed for step 1 is $P_{\text{smooth}}(L_p(\sigma, \gamma), L_p(c, s))^{-1} \cdot L_p(s, c) \cdot t_{\text{test}}$ with $t_{\text{test}}$ the time of a smoothness test. At the time Index Calculus was published $t_{\text{test}}$ used to be important because the test was trial division. But thanks to ECM testing smoothness became sub-exponential, so we can neglect it in $L$ notation. According to the section Sparse Systems step 2 takes time $L_p(s, c)^2 = L_p(s, 2c)$. Therefore steps 1 and step 2 in Index Calculus have complexity:

$$L_p(\sigma - s, (\sigma - s)\frac{\gamma}{c})L_p(s, c) + L_p(s, 2c). \qquad (2.3)$$

We minimize this expression for fixed $\sigma$ and $\gamma$ by taking $s = \frac{\sigma}{2}$ and $c = \sqrt{\frac{\sigma\gamma}{2}}$. Since $\sigma = 1$ and $\gamma = 1$, time(step 1 + step 2)=$L_p(\frac{1}{2}, \sqrt{2})$. One checks that step 3 is negligible, so

$$\text{time}(\text{Index Calculus}) = L_p(\frac{1}{2}, \sqrt{2})^{1+o(1)}.$$

**Remark 1** Every time an algorithm was designed for factorization using smoothness and linear algebra, there was an algorithm for DLP with the same complexity. Nevertheless it does not imply the two problems are connected. It is rather a consequence of reducing both problems to instances of same size of problem 1.

## 2.5 Sieving

We decide to replace choosing random numbers and testing their smoothness by a routine which finds smooth numbers all at once. In this way we save the time for smoothness testing even though it does not count in the $L$ notation of the complexity (and unfortunately uses more space)$^1$. The procedure goes as it follows. First make an array in which the $n^{th}$ position records $[\log_2(n)]$. Then for each prime number $p$ (first untouched entry of the array, not $p$ in DLP) subtract $[\log_2 p]$ from $p, 2p, \dots$, then subtract $\log_2 p$ from $p^2, 2p^2, \dots$ and so on. At the end, the entries of the array which are almost zero correspond$^2$ to smooth numbers. Let's call $A$ the cardinal of the sieving array and we impose the condition $A \ge B$. Then the time needed for a sieve is $A \cdot (\sum_{p \le B} \frac{1}{p})$ which leads$^3$ to a

<footnote>$^1$Pomerance used this idea from Schroeppel to create the Quadratic Sieve. It was a significant advance because at that time smoothness used to be tested by trial division.</footnote>

<footnote>$^2$See [Sil87] for a precise practical analysis.</footnote>

<footnote>$^3$Use the formula $\sum_{p<x} \frac{1}{p} \sim \log \log x$, an easy corollary of the Prime Number Theorem.</footnote>
complexity $A \cdot \log \log(B)$ which is $A^{1+o(1)}$. If we want to find $[L_p(s, c)]$ numbers of size $L_p(\sigma, \gamma)$ which are $L_p(s, c)$-smooth then we need to satisfy the condition $P_{\text{smooth}}(L_p(\sigma, \gamma), L_p(s, c))A \ge L_p(s, c)$. Thus the complexity for solving problem 1 with the sieve is $A^{1+o(1)} = L_p(s, c) \cdot P_{\text{smooth}}(L_p(\sigma, \gamma), L_p(s, c))^{-1}$ which is exactly the complexity of the choose&check strategy.

Next, if we want smooth values for a polynomial $f \in \mathbb{Z}[X]$ we can sieve on pairs $(x, y)$ such that $|x|, |y| \le \sqrt{A}$. For each $x_0$ such that $|x_0| \le \sqrt{A}$ and each prime $p$ we find in polynomial time of $\text{deg}(f)$ and $p$ an $y_0 \le p$ such that $p \mid f(x_0, y_0)$. Then we sieve on $(x_0, y_0), (x_0, y_0 + p), (x_0, y_0 + 2p), \dots$. One can read a detailed proof in [Sch93].

## 2.6 Double smoothness

An important idea is to replace a relation of type $t^h \mod p = p_1^{e_1} \dots p_r^{e_r}$ by two half-equations as below$^4$:

$$ \left\{ \begin{array}{l} \gamma = p_0^{e_0} p_1^{e_1} \dots p_r^{e_r} \\ \gamma = q_0^{f_0} q_1^{f_1} \dots q_s^{f_s} \end{array} \right. \qquad (2.4) $$

The advantage is when $\gamma$, the number we inspect for smoothness, is significantly smaller so we need to repeat the choose&check step less times. In order to obtain two equations like (2.4) one can use for instance imaginary quadratic fields$^5$, i.e $\mathbb{Q}[\sqrt{-s}]$ with $s \in \mathbb{N}$. Suppose one wants to compute the discrete logarithm in $\mathbb{F}_p$. One picks $r$ in $\{-1, -2, -3, -7, -11, -19, -43, -67, -163\}^6$ such that $X^2 - r \equiv 0 \mod p$ has roots in $\mathbb{F}_p$. For example there is 50% chance for one to have $r = -1$ in which case one deals with $\mathbb{Z}[i]$, the Gaussian integers. If no value of $r$ works we use a different algorithm.

The factor base of prime numbers we had in Index Calculus is replaced here by two factor bases: one of prime numbers less than $B$ and one of prime elements in $\mathbb{Z}[\sqrt{r}]$ with norm less than $B$ with $B = [L_p(\frac{1}{2}, \frac{1}{2})]$. Together, the two factor bases have less than $B$ elements since for each rational prime $l$ there are at most

<footnote>$^4$The Gaussian Integers Algorithm is described briefly in [COS86]. It is noticeable that in the same article the authors describe in detail another algorithm of same complexity in the first approximation, but a worse one in a closer look. The better complexity for the Gaussian Integers Algorithm was confirmed in practice since it was the fastest DLP algorithm between 1986 and 1998.</footnote>

<footnote>$^5$The quadratic fields have been used for the first time to compute discrete logarithm in $\text{GF}(p^2)$. See [ElG02]</footnote>

<footnote>$^6$The list is such that $\mathbb{Z}[\sqrt{r}]$ is a unique factorization domain according to Class Number Problem of Gauss which was solved by Stark [Sta07].</footnote>
two primes of $\mathbb{Z}[\sqrt{r}]$ with norm divisible by $l$ and because $\pi(B) < \frac{B}{3}$ for $B > 10$. The pleasant property of $\mathbb{Z}[\sqrt{r}]$ is that the norm is multiplicative, i.e. by putting $N(a+b\sqrt{r}) = a^2-rb^2$ we have $N(xy) = N(x)N(y)$ for all $x, y \in \mathbb{Z}[\sqrt{r}]$. This means we test for smoothness by simply testing the norm for smoothness. Moreover, if we want to factorize an element $x$ we start by factorizing $N(x)$ and then we compute for each prime $l \mid N(x)$ the irreducible elements $l_i \in \mathbb{Z}[\sqrt{r}]$ such that $l_i \mid a$. Indeed, the condition $l_i \mid a$ is equivalent to a system of two linear equations.

The algorithm starts by computing a generator $b = e + f\sqrt{r}$ of the unit group of $\mathbb{Z}[\sqrt{r}]$ which is added to the factor base. Next it finds a root $X_0$ of $X^2 - r \equiv 0 \mod p$, computes a pair $(T, V) \in \mathbb{Z}^2$ such that $T \equiv X_0V \mod p$ and $0 \le T, V < \sqrt{p}^7$ and adds $V$ to the factor base. Let us call $E = L_p(\frac{1}{2}, \epsilon)$ for some parameter $\epsilon$. The algorithm continues by sieving for values of $(c, d) \in [-E, E]$ such that both $cT_0+dV_0$ and $N(c+\sqrt{rd})$ are B-smooth. Since $\mathbb{Z}[\sqrt{r}]$ is here a unique factorization domain and $b$ is a generator of the unit group one can write

$$c + d\sqrt{r} = b^{f_0} l_1^{f_1} \dots l_s^{f_s} \qquad (2.5)$$

for $l_i$ irreducible(prime) elements in $\mathbb{Z}[\sqrt{r}]$. Since $N(c + \sqrt{rd}) = N(l_1)^{f_1} \dots N(l_s)^{f_s}$ and $N(c+\sqrt{rd})$ is B-smooth, the $l_i$ are in the factor base. Similarly, since $cT_0+dV_0$ is B-smooth, one can write:

$$cV + dT = (-1)^{e_0} p_1^{e_1} \dots p_k^{e_k} \qquad (2.6)$$

with the $p_i$ in the rational factor base. Since $T = X_0V$, we have $cV + dT = V(c+X_0d)$. Put $\phi: \mathbb{Z}[\sqrt{r}] \to \mathbb{Z}/p\mathbb{Z}$, $a+b\sqrt{r} \mapsto a+bX_0$. It is a ring homomorphism because both $X_0 \in \mathbb{F}_p$ and $\sqrt{r} \in \mathbb{C}$ are roots of $X^2 - r$. The next system is (2.6) and $V \cdot \phi((2.5))$ and concerns elements of $\mathbb{Z}/p\mathbb{Z}$:

$$\begin{cases} V(c + dX_0) \equiv (-1)^{e_0} p_1^{e_1} \dots p_r^{e_r} \\ V(c + dX_0) \equiv V\phi(b)^{f_0}\phi(l_1)^{f_1} \dots \phi(l_s)^{f_s} \end{cases}$$

The linear algebra step finds the discrete logarithms of the $p_i$, the $\phi(l_i)$, $\phi(b)$ and $V$. This is possible because we don't start the linear algebra step until the number of equations exceeds that of unknown.

Where does the advantage come from? Since $cT_0+dV_0 \le 2\sqrt{p} \cdot E = L_p(1, \frac{1}{2})^{1+o(1)}$ and $N(c+d\sqrt{r}) = \mathcal{O}(1)(c^2+d^2)=L_p(1, \frac{1}{2})^{1+o(1)}$, the pair $(c, d)$ is twice B-smooth with the probability that a number of size $\sqrt{p}$ is B-smooth. Thus the complexity of the Gaussian Integers algorithm is given by the equation 2.3 with $\sigma = 1$ and $\gamma = \frac{1}{2}$. Thus we have:

$$\text{complexity}(\text{Gaussian Integers}) = L(\frac{1}{2}, 1)^{1+o(1)}.$$

<footnote n="7">⁷Finding such $T$ and $V$ is called rational reconstruction of $X_0$ and takes polynomial time. For a proof use theorem 4.3 at page 58 in [Sho09].</footnote>
## 2.7 Number Fields

In section Double smoothness we used fields $K$ such that $[K : \mathbb{Q}] = 2$. Why not to use fields of higher degree? That's exactly what Pollard did in 1988 to factor $2^{128} + 1$, Fermat's 7th number. It is a particular$^8$ case of NFS which we explain in the next lines.

Let $f_1, f_2 \in \mathbb{Z}[X]$ be two monic irreducible polynomials which share a root $m$ in $\mathbb{F}_p$. In what follows $i = 1, 2$. Let's denote $K_i$ the rupture field of $f_i$ and let's call $\alpha_i$ a root of $f_i$ in $K_i$. Let's call $O_i$ the ring of integers in $K_i$. Put $\mathfrak{p}_i = (\alpha_i - m)O_i + pO_i$ which is obviously an ideal above $p$, i.e. which contains $pO_i$. Theorem 2 below shows that $\mathfrak{p}_i$ is prime$^9$ and $O_i/\mathfrak{p}_i \simeq \mathbb{Z}/p\mathbb{Z}$. Therefore one can define $\phi_i : O_i \to \mathbb{Z}/p\mathbb{Z}$, $x \mapsto x \bmod \mathfrak{p}_i$. In particular for all $b_0, \dots, b_{d-1}$ in $\mathbb{Z}$ we have $\phi_i(b_0 + b_1\alpha_i + \dots + b_{d-1}\alpha_i^{d-1}) = b_0 + b_1m + \dots + b_{d-1}m^{d-1} \bmod p$.

Let $a + bX$ be in $\mathbb{Z}[X]$. Then $a + bX$ modulo $f_i$ is in $\mathbb{Z}[X]/\langle f_i \rangle = \mathbb{Z}[\alpha_i] \subset O_i$. Since $\phi_1(a + \alpha_1 b) = a + mb = \phi_2(a + \alpha_2 b)$, the diagram below is commutative.

<figure><img src="image_6.png" /></figure>

### How do we collect pairs of half-equations as in Double smoothness?

Since in general $\mathbb{Z}[\alpha_i]$ is not an UFD, there is no canonical factorization into irreducible elements. Therefore we replace $\mathbb{Z}[\alpha_i]$ by $O_i$ and prime elements by the prime ideals. In this way we keep the unique factorization property because $O_{K_i}$ is a Dedekind domain. A sieve will find many couples $(a, b)$ such that both $N_{K_1}(a+\alpha_1 b)$ and $N_{K_2}(a+\alpha_2 b)$ are smooth. This is possible because $N_{K_i}(a+\alpha_i b) = b^{\text{deg}(f_i)} f_i(-\frac{a}{b})$ is a polynomial in $a$ and $b$.

But the unique factorization is not useful without a way to factorize a principal ideal $\delta O$ into prime ideals. The good news is that there is an algorithm of Buchmann and Lenstra (6.2.2 in [Coh93]) which does so with the same$^{10}$ complexity we need to factor $N_K(\delta)$ into prime numbers.

<footnote>$^8$Pollard used $\mathbb{Z}[\sqrt[3]{2}]$ while in NFS we use arbitrary number fields.</footnote>

<footnote>$^9$We need $p \nmid \text{disc}(f)$ which is easy to obtain.</footnote>

<footnote>$^{10}$If factorization takes time $T$ which is sub-exponential, Buchmann-Lenstra takes time $T \times (\text{polynomial}) = T^{1+o(1)}$ which is the same in $L$ notation.</footnote>
We can even forget about the Buchmann-Lenstra algorithm without changing
the complexity in $L$ notation. Indeed, as it is shown on the diagram 2.7 we only
factor into ideals elements of the form $(a + b\alpha)$. We call badly ramified (or bad)
for $f$ a prime number $l$ such that $l \mid [\mathcal{O}_K : \mathbb{Z}[\alpha]]$. The theorem below shows that
if $N(a + b\alpha)$ does not have badly ramified factors then the time to factor $a + b\alpha$
is the time to factor $N(a + b\alpha)$ times an inversion modulo $p$.

**Theorem 2** Let $a, b$ be coprime integers such that $N(a + \alpha b)$ has no bad factor.
Suppose $N(a + \alpha b) = \Pi_i l_i^{e_i}$ with $l_i$ prime. Then:

(i) For all prime $l$ not badly ramified and $r \in \mathbb{Z}/l\mathbb{Z}$ root of $f$, the ideal $\mathfrak{u}_0 := (\alpha - r)\mathcal{O} + l\mathcal{O}$ is prime and $N(\mathfrak{u}_0) = l$;

(ii) For all $i, b$ is invertible modulo $l_i$. We can put $r_i = -b^{-1}a \mod l_i$ and $\mathfrak{u}_i := (\alpha - r_i)\mathcal{O} + l_i\mathcal{O}$. Then $\mathfrak{u}_i$ is the unique ideal of $\mathcal{O}$ above both $(a - \alpha b)\mathcal{O}$ and $l_i$;

$$
(iii) (a - \alpha b)\mathcal{O} = \Pi_i \mathfrak{u}_i^{e_i}.
$$

proof:

(i) One easily checks that $[\mathbb{Z}[\alpha] : (\mathfrak{u}_0 \cap \mathbb{Z}[\alpha])] = l$. Call $c$ the index $[\mathcal{O} : \mathbb{Z}[\alpha]]$. Since $l$ is not badly ramified, we have $l \nmid c$ and therefore for all $x \in \mathcal{O}$ we have $[x - (c^{-1} \mod l) \cdot c \cdot x] \in l\mathcal{O} \subset \mathfrak{u}_0$. Hence we obtain $[\mathcal{O} : \mathfrak{u}_0] = [\mathbb{Z}[\alpha] : (\mathfrak{u}_0 \cap \mathbb{Z}[\alpha])] = l$. Therefore $\mathfrak{u}_0$ is prime and has norm $l$.

(ii) Since $\gcd(a, b) = 1$ and $N(a+\alpha b) = b^{\deg(f)} f(-\frac{a}{b})$, we have $\gcd(b, N(a+\alpha b)) = 1$ so $r_i$ exists. Since $\alpha - r_i \in \mathfrak{u}_i$ we have $a + \alpha b = (-b) \cdot (\alpha - r_i) \in \mathfrak{u}_i$, so $\mathfrak{u}_i$ is above $a + \alpha b$.

Conversely, let $\mathfrak{u}$ be a prime ideal above $(a - \alpha b)\mathcal{O}$ and $l_i$. Since $l_i \nmid b$, there exists $b' \in \mathbb{Z}$ such that $b'b - 1 \in l_i\mathbb{Z} \subset \mathfrak{u}$. Since $(-b)(\alpha - r_i) = a + \alpha b \in \mathfrak{u}$ we obtain $\alpha - r_i \in \mathfrak{u}$. Therefore we have $\mathfrak{u}_i = (\alpha - r_i)\mathcal{O} + l_i\mathcal{O} \subset \mathfrak{u}$. Since $\mathfrak{u}_i$ is prime (maximal in Dedekind domain), $\mathfrak{u} = \mathfrak{u}_i$.

(iii) We have $N(a + \alpha b) = \Pi_i \Pi_{\text{above } (a+\alpha b)\mathcal{O}} \text{ and } l_i\mathcal{O} N(\mathfrak{u})^{e_i}$ for some integers $e_i$. By (i), $N(a + \alpha b) = \Pi_i N(\mathfrak{u}_i)^{e_i}$. Since $[\mathcal{O} : \mathfrak{u}_i] = l_i$ we have $N(\mathfrak{u}_i) = l_i$ and we conclude $e_i = e_{\mathfrak{u}_i}$. $\square$

Nevertheless, in practice we do not avoid bad primes because it would force
us to loose all the twice-smooth numbers with bad factors. Think about the case
when 2 is bad. Hence we use Buchmann-Lenstra exactly for those numbers with
badly ramified primes.
Why is the complexity of NFS of type $L(\frac{1}{3})$? Number fields bring several obstructions which make the algorithm long, and its rigorous analysis complicated. Still, at this stage of the presentation we can foresee that there is an algorithm and even roughly estimate its complexity. Indeed, the numbers we inspect for smoothness are of size $p$ in Index Calculus and of size $\sqrt{p}$ in the Gaussian Integers. We will see that for the Number Fields we can expect $L_p(\frac{2}{3})$.

In the complexity analysis we need to know the cardinal of the factor bases. Call $B$ the smoothness bound and suppose $deg(K_1), deg(K_2) = O(\log(B)^s)$ for some $s < 1$. Then the union of factor bases has less than $B$ elements$^{11}$. Indeed, there are $\pi(B) \sim B/\log(B)$ prime numbers less than $B$. Each prime number splits into at most $d_i := deg(K_i)$ prime ideals in $K_i$ for $i = 1, 2$. In total $\frac{(d_1+d_2)B}{\log(B)}$ elements. Since $d_1, d_2 = O(\log(B)^s)$ we have $\frac{(d_1+d_2)B}{\log(B)} < B$.

The time spent by the algorithm is of type Proba(smoothness) $\cdot B + B^2$ by analogy with the Gaussian Integers. Let's compute parameters $s, e$ and $\theta$ such that $B = L(s), E = L(e)$ (the sieve bound) and $m = L(\theta)$ optimize the time. For all pair $(a, b) \in \mathbb{Z}^2$ and for $i = 1, 2$ we have $N(a + b\alpha_i) = b^d f_i(-\frac{a}{b}) = O(dL(s)^d|f_i|_\infty)$ where $|f_i|_\infty$ stands for the largest coefficient of $f_i$. We can guarantee $|f_i|_\infty \le m$ by taking $f_1(X) = X - m$ and $f_2(X)$ the base-$m$-expansion of $p$, i.e. $d_2 = d = [\log_m p]$ and $f_2(X) = a_d x^d + a_{d-1}X^{d-1} + \dots + a_0$ with $p = a_d m^d + \dots + a_0$. We can impose $a_d = 1$ by taking $m$ close to $N^{\frac{1}{d}}$ but we do not need this in a first approximation. This choice of polynomials forces us to take $d = \log(p)/\log(m) = \frac{\log(p)^{1-\theta}}{(\log \log p)^{1-\theta}}$. Thus we have $N(a + b\alpha_i) \le L(\max\{e + 1 - \theta, \theta\})$. We minimize the norm for $\theta = \frac{1+e}{2}$. We optimize the sieve if $E = P_{smooth}(L(\frac{e+1}{2}), L(s))^{-1}$ which imposes $e = 1 - 2s$. Hence the sieve takes time $E^2 = L(e)^2 = L(e) = L(1 - 2s)$. Since the linear algebra step takes time $B^2 = L(s)^2 = L(s)$ a trade-off sieve-linear algebra is $s = \frac{1}{3}$. This means that the number we inspect for smoothness, the product norm times absolute value, has size $L_p(\frac{2}{3})$ which is tiny compared to $\sqrt{p}$ for Gaussian Integers. Using equation 2.3 we obtain:

$$ complexity(\text{NFS}) = L(\frac{1}{3}). $$

## 2.8 Virtual Logarithms

### 2.8.1 Preparation

The obstructions of the NFS come from the difference between the output of the sieve and the input of the linear algebra step. Indeed, on the one hand the sieve

<footnote>$^{11}$In practice all our prime ideals are of degree one except those above bad primes. In average a polynomial of given degree has at most one root modulo each prime number, so a thumb rule for the number of prime ideals is $2 \cdot \pi(B)$.</footnote>
finds systems of type:

$$ \left\{ \begin{array}{l} \delta \mathcal{O}_1 = \mathfrak{p}_1^{e_1} \dots \mathfrak{p}_k^{e_k} \\ \delta \mathcal{O}_2 = \mathfrak{q}_1^{f_1} \dots \mathfrak{q}_l^{f_l}. \end{array} \right. $$

On the other hand the linear algebra step needs linear equation of type

$$ e_1 \log(\mathfrak{p}_1)'' + \dots + e_k \log(\mathfrak{p}_k)'' = f_1 \log(\mathfrak{q}_1)'' + \dots + f_l \log(\mathfrak{q}_l)'' \mod q $$

where $q|p-1$ and $\log(\mathfrak{p}_i)''$ is something that we do not know how to define.

There were two solutions found: one is to change what the linear algebra computes, the other is to give a deeper explanation for Index Calculus. In the first, one puts $K_1 = \mathbb{Q}$ and during the linear algebra step computes a vector $\langle x_{(a,b)} | (a, b)$ is double smooth$\rangle$ and an integer $x$ such that $T^x S \Pi_{(a,b)}(a+b\alpha_1)^{x(a,b)} = 1 \mod p$ and $\Pi_{a,b}(a + \alpha_2 b)^{x(a,b)}$ is a $q^{th}$ power. As a consequence $T^{-x} \equiv S \mod p$. The disadvantage is that the linear algebra step depends on $S$, so the individual logarithm is as expensive as the precomputations. This is the case for both Gordon's [Gor93] and Schirokauer's [Sch93] algorithms.

The other solution is to see that the discrete logarithms of the factor base in Index Calculus are nothing but the coordinates of a vector $(l_1, \dots, l_R)$ with $R = \pi(B_1)$ and such that if $S$ is $B_1$-smooth and if we know a factorization $S = p_1^{e_1} \dots p_R^{e_R}$ of $S$ then $\log_T(S) = e_1l_1 + \dots + e_Rl_R$.

Let's be more precise. As usual $p$ denotes the prime in input for DLP and $q$ a prime divisor of $p-1$. Call $S = \{p_1, \dots, p_R\}$ the factor base used in Index Calculus. In the diagram below $K_S = \{p_1^{e_1} \dots p_R^{e_R} | e_1 \dots e_R \in \mathbb{Z}\}$. Call $\phi$ the projection of $\mathbb{Z}$ on $\mathbb{Z}/p\mathbb{Z}$ which induces a map $\phi|_{K_S} : K_S \to \mathbb{F}_p^*$. Put $\bar{\phi} : K_S/K_S^q \to \mathbb{F}_p^*/(\mathbb{F}_p^*)^q$ the obviously induced map. Put $\psi(x) = (\mathrm{val}_{p_1}(|x|), \dots, \mathrm{val}_{p_{|S|}}(|x|))$ which gives an isomorphism $\psi : K_S \to (\mathbb{Z}/q\mathbb{Z})^{|S|}$ and call $E = (\mathbb{Z}/q\mathbb{Z})^{|S|}$ which is a $\mathbb{F}_q$-vector space. Finally put $\bar{\psi} : K_S/K_S^q \to (\mathbb{Z}/q\mathbb{Z})^{|S|}$ the obviously induced map.

<figure><img src="image_7.png" /></figure>

Let's put $\varphi = l_t \circ \bar{\psi}^{-1}$ and notice that we have $\varphi \in E^*$. Now we understand Index Calculus in a different way: during the chose&check step we collect $|S| + k$, $k = O(1)$, pairs $(v_i, \varphi(v_i))_{1 \le i \le |S|+k}$ and for heuristic reasons we expect the family $(v_i)_{1 \le i \le |S|+k}$ to have rank $|S|$. The linear algebra step is finding the matrix of $\varphi$ from the values $\varphi$ takes on a base. Finally the step 3 in Index Calculus is finding a relation between $S$ and an element $S'$ in $K_S$, computing the exponent vector
$e = \bar{\psi}(S')$ and obtaining $\overline{\log_T}(S') = \varphi(e)$. In short, steps 1 and step 2 find the horizontal vector in the next equation while step 3 finds the vertical one.

$$ \log_T(|S|) = (\log_T(2) \dots \log_T(p_R)) \cdot \begin{pmatrix} e_1 \\ \vdots \\ e_R \end{pmatrix}. \qquad (2.7) $$

Notice that we compute the discrete log of $|S|$ instead of $S$ since one can check that $\log_T(-1) = \frac{p-1}{2}$. The case of $-1$ is explained below together with the other roots of unity.

### 2.8.2 Schirokauer's maps

Let $q$ denote as usual a prime divisor of $p-1$ and $K$ a number field (one of the two or more used in NFS). In the sequence we suppose $q^2 \nmid p-1$ and $q \nmid h_K$, the class number of $K$. Indeed, if $q \le L_p(\frac{1}{3}, 2)$ then we use the Pollard's Rho method<fnref n="12" /> instead of NFS, so we don't need Schirokauer's maps. If $q$ is larger we have a probability<fnref n="13" /> of at least $(1 - \frac{1}{q})$ that $q$ does not divide the class group order of $K$. It is then reasonable in practice to forget about the case $q \mid h_K$. In theoretical study if this case occurs we run again the whole algorithm for a different polynomial $f$. It does not change the asymptotic complexity. A second difficulty comes if $q^e \mid p-1$ with $e \ge 2$. In this case the algorithms must be adjusted, but the modifications are short and they are described in detail in [Sch93].

Remember Dirichlet's Theorem which says that $O_K^*$ is isomorphic to $\mu \times \mathbb{Z}^{r_R+r_C-1}$ where $(r_R, r_C)$ is the signature<fnref n="14" /> of $K$ and $\mu$ is the group of roots of unity. If $gcd(\#\mu, q) = 1$, then<fnref n="15" /> $O^*/(O^*)^q \simeq (\mathbb{Z}/q\mathbb{Z})^{r_R+r_C-1}$. As it comes to roots of order $q$, we avoid them by imposing $q \nmid \text{disc}(f)$ when we select $f$ (in practice we ignore them). The lemma below makes it clear:

**Lemma 1** Let $f$ be an irreducible polynomial in $\mathbb{Q}[X]$ and $K$ its rupture field. If $q$ is an odd prime number such that $q \nmid \text{disc}(f)$, then $K$ has no roots of unity of order $q$.

*proof* Suppose $\xi_q \in K$ is a $q^{th}$ root of unity. Then $\mathbb{Q}(\xi_q) \subset K$. As a consequence all the prime numbers ramified over $\mathbb{Q}(\xi_q)$ are ramified over $K$. It is known that $|\text{disc}(\mathbb{Q}(\xi_q))|$ is a power of $q$, so $q$ is ramified over $\mathbb{Q}(\xi_q)$, thus over $K$. Therefore

<footnote n="12">¹²Despite the bad complexity of Pollard's Rho, it is still fast enough. Indeed $\sqrt{q} \le L(\frac{1}{3}, 2)^{\frac{1}{2}} = L(\frac{1}{3}, 1)$.</footnote>

<footnote n="13">¹³See [CL84] for heuristics on the class group number.</footnote>

<footnote n="14">¹⁴$K$ has $r_R$ embeddings in $\mathbb{R}$ and $2r_C$ more in $\mathbb{C}$. Remember that $r_1 + 2r_2 = d$.</footnote>

<footnote n="15">¹⁵One can check that the roots of unity are all $q^{th}$ powers. It makes the condition Schirokauer [Sch05] puts when defining virtual logs superfluous.</footnote>
$q$ divides $disc(K)$ and since $disc(K)^2[\mathcal{O}_K : \mathbb{Z}[\alpha]] = \pm disc(f)$, we deduce that $q$ divides $disc(f)$. $\square$

Now that we know there is an isomorphism $O^*/(O^*)^q \simeq (\mathbb{Z}/q\mathbb{Z})^r$ with $r := r_{\mathbb{R}} + r_{\mathbb{C}} \le d$ we want to compute it. The naive idea is to map $O^*$ in $\mathbb{R}^r$ by $x \mapsto (\log|\psi_1(x)|, \dots, \log|\psi_r(x)|)$ where $\psi_i$ are embeddings of $K$ into $\mathbb{C}$. Unfortunately we do not know how to use this idea without executing the linear algebra step over $\mathbb{Z}$. If we do so even a sparse system like ours costs $O(B^3)$ with $B$ the size of the system and we obtain a poorer complexity. For example Gordon [Gor93] obtained $L_p(\frac{1}{3}, 2.080)$ for his discrete log by NFS. Instead we define $r$ maps $(\lambda_1, \dots, \lambda_r) : O^* \to (\mathbb{Z}/q\mathbb{Z})^r$ such that the only $x$ which verify $(\lambda_1(x), \dots, \lambda_r(x)) = (0, \dots, 0)$ are the $q^{th}$ powers.

**Definition 2** Let $q$ be a prime factor of $p-1$ which is unramified$^{16}$ over $K$ and pick a base $b$ of the free $\mathbb{Z}$-module $\mathcal{O}_K$. Let $f = \Pi_{i \le k} f_i$ be the decomposition of $f$ in $\mathbb{F}_q$ and $\epsilon = \text{lcm}\{\text{deg} f_i, 1 \le i \le k\}$. In the lemma below we show that $\lambda : \mathcal{O}_K^*/(\mathcal{O}_K^*)^q \to q\mathcal{O}_K/q^2\mathcal{O}_K$, $u \mapsto u^\epsilon - 1 \bmod q^2\mathcal{O}_K$ is a well defined homomorphism. We call maps of Schirokauer the coordinates $\lambda_1, \dots, \lambda_d$ of $\lambda$ in the base $b$.

Notice that one computes the maps of Schirokauer in polynomial time. Also notice that we defined $d$ maps of Schirokauer while we announced that $r$ of them are enough. This is because the theorem below shows that the application $(\lambda_1, \dots, \lambda_d) : \mathcal{O}_K^*/(\mathcal{O}_K^*)^q \to (\mathbb{Z}/q\mathbb{Z})^d$ has rank $r$ and therefore one can select in polynomial time $r$ indices $i_1, \dots, i_r$ such that $\text{ker}(\lambda_1, \dots, \lambda_d) = \text{ker}(\lambda_{i_1}, \dots, \lambda_{i_r})$. So, the application $(\lambda_{i_1}, \dots, \lambda_{i_r}) : \mathcal{O}_K^*/(\mathcal{O}_K^*)^q \to (\mathbb{Z}/q\mathbb{Z})^r$ is what we need.

**Lemma 2** The map $\lambda : \mathcal{O}_K^*/(\mathcal{O}_K^*)^q \simeq q\mathcal{O}_K/q^2\mathcal{O}_K$, $u \mapsto u^\epsilon - 1 \bmod q^2\mathcal{O}_K$ is a group homomorphism.

*proof:* Let $\gamma, \gamma' \in \mathcal{O}_K^*$. For all $1 \le i \le k$, $\mathfrak{q}_i = q\mathcal{O}_K + (f_i)\mathcal{O}_K$ is prime and $\mathcal{O}_K/\mathfrak{q}_i \simeq \mathbb{F}_{q^{\text{deg}(f_i)}}$. Thus, for all $1 \le i \le k$ $\gamma^\epsilon \equiv 1 \bmod \mathfrak{q}_i$. Then, by Chinese Remainder Theorem, $\delta^\epsilon \equiv 1 \bmod \Pi_i \mathfrak{q}_i$, i.e. modulo $q\mathcal{O}_K$ because $q$ is unramified. Therefore there exist $\delta \in \mathcal{O}_K$ such that $\gamma^\epsilon = 1 + q\delta$. Similarly there exist $\delta' \in \mathcal{O}_K$ such that $\gamma'^\epsilon = 1 + q\delta'$. Then we have: $(\gamma\gamma')^\epsilon = 1 + q(\delta + \delta') + q^2(\dots)$. Therefore $\lambda$ is a homomorphism. $\square$

The main theorem about Schirokauer's maps is as follows.

**Theorem 3** Let $q$ be a prime factor of $p-1$ which is unramified over $K$. Suppose $q \nmid p-1$, $q \nmid h_K$ and $[(\mathcal{O}_K)^* \cap (1+q^2\mathcal{O}_K)] \subset (\mathcal{O}_K^*)^q$. Let $\gamma \in \mathcal{O}_K$ be such that:

(i) $\text{ord}_p(\gamma) \equiv 0 \pmod{q\mathbb{Z}}$ for all prime ideal $p$;

<footnote>$^{16}$The case $q$ ramified makes no difference for the implementation, accepts a proof as long as in the unramified case, but it makes exposition less clear. For details see [Sch93]. If one wanted to avoid $q$ to be ramified, one would only need to impose $q \nmid disc(f)$ when selecting $f$.</footnote>
(ii) $\lambda(\gamma) = 0$.

Then $\gamma$ is a $q^{th}$ power.

*proof* It is proposition 3.8 in [Sch93].

It means that, subject to the conditions of the theorem, Schirokauer's maps provide us with an isomorphism $O^*/((O^*)^q) \to (\mathbb{Z}/q\mathbb{Z})^r$. The only condition which wasn't analyzed is the last one: $(O_K)^* \cap (1 + q^2O_K) \subset (O_K^*)^q$. Unfortunately we do not have an equivalent condition easy to test. It makes algorithms using Schirokauer's maps heuristic. Nevertheless algorithms work in practice and Schirokauer [Sch93] proved that it comes to a matrix over $\mathbb{F}_q$ with seemingly random entries to be invertible.

### 2.8.3 Definition of the virtual logs

We draw once again the diagram in the preparation but we generalize the notations. Let $K$ be $K_i$ with $i = 1, 2$, $r = r_i$ the free rank of $O_{K_i}^*$ and $\phi = \phi_i$ where $\phi_i$ is the function defined in section 2.7. Call $S$ the set of prime ideals of $K$ which we use as factor base. Put $K_S = \{\gamma \in O_K | \text{ all the ideal factors of } \gamma O_K \text{ are in } S\}$. Let $\phi: K_S \to \mathbb{F}_p$ be the restriction of $\phi$ to $K_S$. Put $\bar{\phi}: K_S/K_S^q \to \mathbb{F}_p^*/(\mathbb{F}_p^*)^q$ the obviously induced map. We put $\psi(x) = (\text{val}_{p_1}(x), \dots, \text{val}_{p_{|S|}}(x), \lambda_1(x), \dots, \lambda_r(x))$ where the $\lambda_j$ are Schirokauer's maps. We obtain an isomorphism $\psi: K_S \to (\mathbb{Z}/q\mathbb{Z})^{|S|+r}$. Call $E = (\mathbb{Z}/q\mathbb{Z})^{|S|+r}$ which is a $\mathbb{F}_q$-vector space. Put $\bar{\psi}: K_S/K_S^q \to (\mathbb{Z}/q\mathbb{Z})^{|S|+r}$ the induced map. Let $\text{log}_T$ be the discrete logarithm and $\overline{\text{log}}_T$ be $\text{log}_T \mod q$. Finally put $l_T = \overline{\text{log}}_T \circ \bar{\phi}$ which can be called the discrete logarithm modulo $q$ of numbers in $O_K$.

<figure><img src="image_8.png" /></figure>

For $i = 1, 2$ we define $\varphi_i$ as in the diagram. We can now define the following linear map: $\varphi: \mathbb{F}_q \times \mathbb{F}_q^{|S_1|+r_1} \times \mathbb{F}_q^{|S_2|+r_2} \to \mathbb{F}_q, \varphi(k, x, y) = k + \varphi_1(x_1, \dots, x_{|S_1|+r_1}) - \varphi_2(y_1, \dots, y_{|S_2|+r_2})$. We know the value of $\varphi(1, 0, 0)$ which is 1. We also know $|S_1| + |S_2| + r_1 + r_2$ vectors in $\text{ker}(\varphi)$. One of them is $(1, \psi(x), 0)$ obtained from $\tau O_{K_1} = \Pi \mathfrak{p}_i^{e_i(t)}$ where $\tau \in O_{K_1}$ is such that $\phi_1(\tau) = T$. The others are of type $(0, \psi_1(a + \alpha_1 b), \psi_2(a + \alpha_2 b))$.

**Definition 3** The coordinates $(\chi_{\mathfrak{p}_1}, \dots, \chi_{\mathfrak{p}_{|S|_1}}, \chi_1, \dots, \chi_{r_1}, \chi_{q_1}, \dots)$ of $\varphi$ are called virtual logarithms. In particular $\chi_{\mathfrak{p}}$ is the virtual log of $\mathfrak{p}$ and $\chi_j$ is the virtual log of the $j^{th}$ map of Schirokauer.
We call virtual logarithms like this because we compute them in the same way we used to compute the discrete logs of small primes in Index Calculus. Nevertheless we do not know any interpretation of them as logarithms. Notice that we have:

$$ \forall s, \log_t(s) = ( \chi_{p_1} \cdots \chi_{p_{|S_1|}} |\chi_1 \cdots \chi_{r_1}| \chi'_{q_1} \cdots \chi'_{q_{|S_2|}} |\chi'_1 \cdots \chi'_{r_2} ) \cdot \begin{pmatrix} e_1(s) \\ \vdots \\ e_{|S_1|}(s) \\ \lambda_1(s) \\ \vdots \\ \lambda_{r_1}(s) \\ f_1(s) \\ \vdots \\ f_{|S_2|}(s) \\ \lambda'_1(s) \\ \vdots \\ \lambda'_{r_2}(s) \end{pmatrix} . \quad (2.8) $$

In the past lines we stated without proof results which together make a demonstration of the following theorem.

**Theorem 4** Let $K_1$ and $K_2$ be two number fields without $q^{th}$ roots of the unity. Define $\psi_1$ respectively $\psi_2$ like on the diagram above. Then we have:

(i) For each $i = 1, 2$ and for each set of prime ideals $S_i$ there is a unique vector $\varphi_i$ which makes the diagram above commutative. It defines for each pair $(S_1, S_2)$ a linear form $\varphi$ as above.

(ii) If $S'_1 \subset S_1$ is a different prime ideals set then $\varphi'_1$ is the restriction of $\varphi_1$ to a subspace. In particular if $\mathfrak{p} \in S'_1 \subset S_1$, then the coefficient $\chi_{\mathfrak{p}}$ of $\varphi$ is equal to the coefficient $\chi'_{\mathfrak{p}}$ of $\varphi'$.

(iii) Suppose in addition we have a family $\{(a, b)|a, b \in \mathbb{Z}\}$ such that $\{(0, \psi_1(a + \alpha_1 b), \psi_2(a + \alpha_2 b))\}$ has rank $|S_1| + |S_2| + r_1 + r_2 - 1$, i.e. the sieve step managed to find a full rank family. Then the linear system $\{\varphi(1, \psi(x), 0) = 1, \forall (a, b), \varphi(0, \psi_1(a + \alpha_1 b), \psi_2(a + \alpha_2 b)) = 0\}$ has exactly one solution: the coefficients of $\varphi$.

It can be surprising that the definition of the virtual logarithms used the sets $S_i$ since we proved later that the virtual logs are independent. The reason is that we could have given an equivalent definition like the one in proposition 3.4 in [Sch05]: $\chi_q = [l_T(\theta) - \sum_{j=1}^r \chi_j \lambda_j(\theta)] \cdot h_K^{-1} \mod q$ for any $\theta$ such that $\theta O_K = q^{h_K}$. Nevertheless our definition is more algorithmic-oriented.
Notice that (i) is a rephrasing of theorem 3.2 in [Sch05]. In the same paper Schirokauer pointed out that a failure of $\psi_1$ or $\psi_2$ to be isomorphisms, i.e. a failure for the heuristics we made on Schirokauer's maps, cannot be detected until the whole algorithm has been run.<fnref n="17" /> It should be also noted that the virtual logarithms depend on Schirokauer's maps which in turn depend on the bases of $O_{K_i}$ we use. Therefore if one records the virtual logs for later individual log computations, one needs to record also the Schirokauer's maps used.

An important property of the virtual logarithms is (ii), especially the uniqueness of the coefficients $\chi_j$ corresponding to Schirokauer's maps. Indeed, in some algorithms like the descent by special $Q$ we compute the coefficients $\chi_j$ using a small set $S_1$ but we use equation 2.8 for numbers with prime ideal factors of large norm.

## 2.9 Factorization Factory<fnref n="18" />

Thanks to the Virtual logarithms the linear algebra step depends only on $p$ which means we can re-use it for many individual logarithms. Unfortunately we cannot share the linear algebra step for several values of $p$ since its result, the virtual logarithms, are strongly related to $p$. Nevertheless Coppersmith [Cop93] showed that we can share part of the sieving step. Indeed the algorithm works as soon as we have $m = L_p(\frac{2}{3}, \frac{1}{\delta})^{1+o(1)}$ which allows us to use the same $m$ for all the primes $p$ in $[p_0, p_0 \cdot L_{p_0}(\frac{2}{3}, \frac{1}{\delta})]$ with $p_0$ fixed. Since the sieve is easier, we can ask for smooth numbers of better quality, i.e. we can lower $B$. Therefore the matrix in the linear algebra step is smaller and we will obtain a complexity of $L_p(\frac{1}{3}, 1.639)$ for the precomputations. For now 18 years this algorithm has had only a theoretical purpose since it requires space $L_{p_0}(\frac{1}{3}, 1.639)$.

Let's make the computations. We use two number fields $K_1 = \mathbb{Q}$ and $K_2$ and a unique smoothness bound $B$. Let $\beta$ and $\delta$ be parameters such that $B = [L_p(\frac{1}{3}, \beta)]$ and $d = [\delta(\log p)^{\frac{1}{3}}(\log \log p)^{-\frac{1}{3}}]$. Let $\epsilon$ be such that the permanent file records all pairs $(a, b)$ with $|a|, |b| \le L_{p_0}(\frac{1}{3}, \epsilon)$, $\gcd(a, b) = 1$ and such that $a + bm_0$ is B-smooth. Notice that $m_0$ is the value of $m$ computed for $p_0$ and is shared for all $p$ such that $\log_2(p_0) \le \log_2(p) \le \log_2(p_0) + \frac{1}{\delta}\log(p_0)^{2/3}\log\log(p_0)^{1/3}$. One checks that the probability $P_2$ for $(a + b\alpha)$ to be B-smooth is $L_p(\frac{1}{3}, \frac{\frac{1}{\delta}+\delta\epsilon}{3\beta})^{-1+o(1)}$. In the same way one computes $P_1$ the probability of $a + bm_0$ to be B-smooth $L_p(\frac{1}{3}, \frac{1}{3\delta\beta})^{-1+o(1)}$. The condition for the algorithm to succeed is that it finds enough relations, i.e.

<footnote n="17">¹⁷Conversely a success of the algorithm does not guaranty that the functions $\psi_i$ are isomorphisms.</footnote>

<footnote n="18">¹⁸The term "factorization factory" was coined by Coppersmith in [Cop93].</footnote>
$E^2P_2P_1 \ge B$. This is:

$$2\epsilon - \frac{2}{3\delta\beta} - \frac{\epsilon\delta}{3\beta} \ge \beta. \qquad (2.9)$$

The time of step 1 is $BP_2^{-1}$ since the time to test smoothness is negligible. The time for step 2 is $L_p(\frac{1}{3}, 2\beta)^{1+o(1)}$ as in the other versions of NFS. Therefore we want to minimize:

$$\max(2\beta, \beta + \frac{1}{3\beta\delta} + \frac{\epsilon\delta}{3\beta}). \qquad (2.10)$$

We impose equality in 2.9 because a smaller sieving domain means a faster sieve and because equality means the smallest value for $\epsilon$ except if $\delta > 6\gamma$. The case $\delta > 6\gamma$ transforms our condition into a tautology which cannot be the case, so this case does not translate any practical situation. We also impose:

$$2\beta = \beta + \frac{1}{3\beta\delta} + \frac{\epsilon\delta}{3\beta}. \qquad (2.11)$$

Indeed, when one minimizes $\max(x, f(x))$ for some decreasing function $f$, on an open domain, one takes $x = f(x)$. Otherwise a small change of $x$ would diminish the maximum in both cases $x > f(x)$ and $x < f(x)$. We did not prove that the time of the sieve is decreasing with the smoothness bound $B$, but we do not want to prove that we make the best choices of parameters. If one computes $2 \cdot (2.9) + (2.11)$, one obtains:

$$\epsilon = \frac{9\beta^2}{6\beta + \delta}. \qquad (2.12)$$

Put $s = \frac{\epsilon}{\beta}$ and $t = \frac{\delta}{\beta}$. Then (2.12) becomes $s = \frac{9}{6+t}$ and the equality version of (2.9) becomes $\beta^3 = [s(2 - \frac{t}{3}) - 1]\frac{3}{2}t$. What we try to minimize is $2\beta = 2\sqrt[3]{h(t)}$ with $h(t) = \frac{6t(3-t)}{6+t}$. By derivation one finds that the optimal choice is $t = 3\sqrt{6} - 6$. Therefore $\beta = (\frac{5+2\sqrt{6}}{18})^{\frac{1}{3}} \approx 0.8193$, $\delta = \beta(3\sqrt{6} - 6) \approx 1.1048$ and $\epsilon = \beta \cdot \frac{\sqrt{6}}{2} \approx 1.0034$. This gives time $L_p(\frac{1}{3}, 2\beta)^{1+o(1)} = L_p(\frac{1}{3}, 1.639)^{1+o(1)}$ for steps 1 and 2 and $L_{p_0}(\frac{1}{3}, 2\epsilon)^{1+o(1)} = L_{p_0}(\frac{1}{3}, 2.007)$ for the pre-sieving procedure.

**Remark 2** We did not use the idea of multiple number fields here. Indeed using $V$ fields multiplies the size of the linear system by $V$. Therefore we need to divide the smoothness bound by $V$. By computations one sees that the probability of a number to be $B/V$-smooth for one of $V$ fields is smaller than the it's probability to be $B$-smooth for the first field. Indeed the probability is of type $u^{-u}$ rather than $u^{-const.}$. This is not the first time we see the bad effect of multiple fields. In Coppersmith's modification to NFS we have a good idea-sharing the rational sieve- which should win us much of the time used for sieving. Nevertheless, the bad effect of multiple fields annihilated part of our gain so that we only have a speed-up from $L_p(\frac{1}{3}, 1.923)$ to $L_p(\frac{1}{3}, 1.902)$.
## 2.10 Descent by Special Q

All the improvements previously presented speed up the precomputation stage. Therefore we need a new idea to speed up the individual logarithm from $L(\frac{1}{2})$ to $L(\frac{1}{3})$. We proceed as it follows. First pick $h$ in the factor base and choose&check random $z$ until $h^zS$ is $L_p(\frac{2}{3})$-smooth. Then write $h^zS = q_1...q_2$ and compute the virtual logarithms of the $q_i$ by a descent<fnref n="19" /> as it follows. Let $Q$ be the number of size $L_p(\frac{2}{3})$ we want to write in $\mathbb{F}_p$ as a product of numbers of size $L_p(\frac{1}{3})$. Choose a parameter $\nu \in (0,1)$ and sieve on the numbers of form $a+bm$, with $|a|, |b| \le L_p(\frac{1}{3})Q^{\frac{1}{2}}$ and which are divisible by $Q$ for those for which both $\frac{a+bm}{Q}$ and $a+b\alpha$ are $Q^\nu$-smooth. We obtain a system:

$$ \left\{ \begin{array}{l} a+bm = Q\Pi l^{e_{Q,l}} \qquad l \le Q^{\nu}, \text{prime} \\ (a+b\alpha)\mathcal{O}_{K_2} = \Pi \mathfrak{u}^{m_{Q,u}} \qquad N(\mathfrak{u}) \le Q^{\nu}, \mathfrak{u} \text{ ideal in } K_2. \end{array} \right. $$

This gives us an equation:

$$ \log_T Q \equiv \sum_{u} \chi_u m_{Q,u} + \sum_{k=1}^{r} \chi_k \lambda_k (a+b\alpha) - \sum_{l} \log_T l \mod q \quad (2.13) $$

with $\chi_u$, $\chi_k$ and $\log_T l$ defined in 2.8.3. Then start again with each divisor $l$ of $a+bm$ respectively each prime ideal divisor of $a+b\alpha$. Notice that we make descents for both numbers and ideal even if we started with a number.

The probability of a number $a+bm$ to be $Q^\nu$-smooth is at least $P_{\text{smooth}}(L(\frac{2}{3}), L(\frac{1}{3}))$ which is $L(\frac{1}{3})^{-1}$. Next the probability that $a+b\alpha$ is $Q^\nu$-smooth is $P_{\text{smooth}}(L(\frac{1}{3})Q^{\frac{1}{2}}, Q^\nu)$. This is the lowest when $Q$ has size $L(\frac{1}{3})$ and it is $L(\frac{1}{3})^{-1}$. As a consequence we descend from the size of $Q$ to the size of $Q^\nu$ after testing for smoothness $L(\frac{1}{3})$ pairs. One checks easily that the number of steps in the descent is $O(e^{(\log \log p)^2})$, which gives the descent step a complexity of type $L(\frac{1}{3})$. See subsection 3.3.2 for full details.

<footnote n="19">¹⁹The idea of descent is present in [Cop02]. Joux and Lercier used in practice a particular case of descent without supplying theoretical analysis. They also suggested to perform it using Pollard's Lattice Sieve introduced in [Pol93]. Commeine and Semaev adapted the idea to NFS and proved that it has a complexity of $L(\frac{1}{3}, 1.442)$.</footnote>
# Chapter 3

## New Algorithm: Discrete Logarithm Factory

### 3.1 The algorithm

The algorithm we are going to present combines all the ideas above and has complexity $L_p(\frac{1}{3}, 1.639)$ for the precomputations and $L_p(\frac{1}{3}, 1.232)$ for the individual logarithm. The algorithm uses a file of size $L_{p_0}(\frac{1}{3}, 1.639)$ computed after a presieving procedure which has complexity $L_{p_0}(\frac{1}{3}, 2.007)$.

<caption>**Algorithm 2 Discrete Logarithm Factory**</caption>

REQUIREMENTS: a prime $p_0$ and the values for $\delta = 1.1048$, $\beta = 0.8193$, $\epsilon = 1.0034$, $B = L_{p_0}(\frac{1}{3}, \beta)$, $E = L_{p_0}(\frac{1}{3}, \epsilon)$, $d = [\delta(\log p_0)^{\frac{1}{3}}(\log \log p_0)^{-\frac{1}{3}}]$, $c = 0.811$, $C = L_{p_0}(\frac{2}{3}, c)$, $\bar{c}_M = c_M^1 = 1$; $m_0 = [L_{p_0}(\frac{2}{3}, \frac{1}{\delta})]$; a permanent file with the couples $(a, b)$ such that $a + m_0b$ is B-smooth.

INPUT: $p$ of size $p_0$ and $T, S \in \mathbb{F}_p^*$ such that $T$ spans $\mathbb{F}_p^*$ and $T$ is B-smooth over $\mathbb{Z}$; a prime factor $q$ of $p-1$.

OUTPUT: $\log_T S$ modulo $q$.

0. Select $f \in \mathbb{Z}$ irreducible such that $p \mid f(m_0)$ and $|f|_\infty \le m_0$; set $K_1 = \mathbb{Q}, K_2 = \mathbb{Q}[X]/\langle f \rangle$.

#### (*) PRECOMPUTATIONS

<footnote n="1">¹$\bar{c}_M$ does not count in first approximation complexity. One has to find the best value in practice.</footnote>
1.1 SIEVE: Sieve on the polynomials $\{a + bX \mid a, b \text{ in the permanent file}\}$ until B pairs $(a, b)$ are B-smooth $O_{K_2}$;

1.2 LINEAR ALGEBRA: Compute the virtual logarithms by solving the linear system.

(**) INDIVIDUAL LOG

2.1 SMOOTHING: Take h a prime from the factor base over $\mathbb{Q}$; choose and check random z until $h^z S$ is C-smooth; factorize $h^z S = q_1q_2\dots q_k$;

2.2 DESCENT: For each $j \le k$ do descent steps in order to express $\log_T q_j$ with respect to the virtual logarithms computed in step 1.2.

## 3.2 Admissibility

### 3.2.1 The early abort selection method

We are given a generator of random integers in $[1, n]$ and we need to find one element which is $L_n(\frac{2}{3}, a)$-smooth, for a value $a > 0$ we prefer. If $a$ is too small, the probability of success is too small. If $a$ is too large, then the smoothness test is slow because its time depends mostly on the smoothness bound. We will give the best value for $a$ at the end of the analysis, but for the moment it is a parameter. Contrary to the naive technique, according to which one inspects every number for $L_n(\frac{2}{3}, a)$-smoothness, we proceed in two steps. First we submit each number to a quick test called *admissibility*, which discards most of the bad candidates and some of the good ones. The candidates who succeed the first test are called *admissible* and are submitted to the actual test of $L_n(\frac{2}{3}, a)$-smoothness. The numbers who succeed both tests are called *admitted* and are obviously good candidates. We show next that a good choice of the admissibility test allows us to asymptotically speed up the selection.

Let $0 < \theta, c < 1$ be parameters which will be chosen later. For all numbers $m \le n$ we put $m_1$ the largest divisor of $m$ which is $L_n(\frac{2}{3}, \theta a)$-smooth. Let us call $M_{ble}$ the set of admissible candidates:

$$M_{ble} = \{m \le n \mid m_1 \ge n^c\}. \qquad (3.1)$$

Next, we define the set of admitted candidates:

$$M_{ed} = \{m \in M_{ble} \mid m \text{ is } L(\frac{2}{3}, a)\text{-smooth}\}. \qquad (3.2)$$

In order to evaluate the cardinals of $M_{ble}$ and $M_{ed}$ we need the next theorem.
**Notation 1** For all $x, y, z$ we put

$$T(x, y, z) = \{m \le x \mid \text{for all prime divisors } p \text{ of } m, z \le p \le y\}.$$

We put $\psi(x, y, z) = \#T(x, y, z)$ and $P_{\text{smooth}}(x, y, z) = \frac{\psi(x, y, z)}{x}$. Finally, for all $n$, $L_n$ or simply $L$ stays for $L_n(\frac{2}{3}, 1)$.

**Theorem 5** Let $\alpha > 0$ be a constant. For all $x, y \ge 10$ we put $u(x, y) = \frac{\log x}{\log y}$. For all $x$, put $Y(x) = [(\log x)^{1+\alpha}, \exp(\log x)^{1-\alpha}]$ and for all pair $(x, y)$ put $Z(x, y) = [1, y^{1-\frac{1}{\log u(x,y)}}]$. Then there exists a function $(x, y, z) \mapsto \epsilon(x, y, z)$ such that we have:

(i) $(\sup_{y \in Y(x), z \in Z(x, y)} |\epsilon(x, y, z)|) \to 0$ as $x$ goes to the infinity.

(ii) for all $x \ge 10, y \in Y(x)$ and $z \in Z(x, y)$, $\psi(x, y, z) = x \cdot u(x, y)^{-u(x,y)(1+\epsilon(x,y,z))}$.

*proof:* It is theorem 2.2. in [Pom82]. The proof uses theorem [CEP83].

A convenient corollary translates the theorem in the $L$ notation:

**Corollary 2** Let $n \in \mathbb{N}$. Let $x = L_n(s_x, c_x)$, $y = L_n(s_y, c_y)$ and $z = L_n(s_z, c_z)$ such that $0 < s_y < s_x$ and $(s_z, c_z) < (s_y, c_y)$ in lexicographical order. Then $\psi(x, y, z) = x \cdot L_n(s_x - s_y, -(s_x - s_y)\frac{c_x}{c_y})^{1+o(1)}$ with $o(1)$ depending on $n$.

The following lemma says that the probability to be smooth decreases as the numbers get larger.

**Lemma 3** Let $(x, y, z) \mapsto \epsilon(x, y, z)$ be a function like in theorem 5. Let $a, \theta, c \in (0, 1)$ be constants. For all $n \ge 10$, put $\bar{\epsilon}(n) = \sup_{x \in [n^c, n]} |\epsilon(x, L^{\theta a}, 1)|$ and $u(n) = \frac{c \log n}{\theta a \log L}$. Then we have:

(i) $\bar{\epsilon}(n) \to 0$ when $n$ goes to infinity.

(ii) For all $n \ge 10$ and all $x$ integer in $[n^c, n]$, $P_{\text{smooth}}(x, L^{\theta a}, 1) \le u(n)^{-u(n)(1-\bar{\epsilon}(n))}$.

*proof:* (i) Let $n \in \mathbb{N}$. For all $x \in [n^c, n]$, we easily check $y := L_n^{\theta a} \in Y(x)$ and obviously $1 \in Z(x, y)$. Hence it holds:

$$\{(x, L^{\theta a}, 1) \mid x \in [n^c, n]\} \subset \{(x, y, z) \mid x \in [n^c, n], y \in Y(x), z \in Z(x, y)\}.$$

Moreover, we have: $[n^c, n] \subset [n^c, \infty)$. Thus, we obtain:

$$\sup_{x \in [n^c, n], y = L^{\theta a}, z = 1} |\epsilon(x, y, z)| \le \sup_{x \ge n^c, y \in Y(x), z \in Z(x, y)} |\epsilon(x, y, z)|. \quad (3.3)$$

From point (i) of theorem 5 we deduce that the right side expression above tends to 0 as $n$ goes to infinity. Thus, we obtain the result.
(ii) Let $x \ge n^c$. From theorem 5 we have:

$$P_{\text{smooth}}(x, L^{\theta a}, 1) = \left( \frac{\log x}{\theta a \log L} \right)^{-\frac{\log x}{\theta a \log L} (1+\epsilon(x, L^{\theta a}, 1))}.$$

Then, by using the definition of $\bar{\epsilon}(n)$, we obtain:

$$P_{\text{smooth}}(x, L^{\theta a}, 1) \le \left( \frac{\log x}{\theta a \log L} \right)^{-\frac{\log x}{\theta a \log L} (1-\bar{\epsilon}(n))} \quad (3.4)$$

We remark that the function $t \mapsto t^{-t}$ is decreasing on $[1, \infty)$. Since $x \ge n^c$, we have $\frac{\log x}{\theta a \log L} \ge \frac{c \log n}{\theta a \log L} = u(n) > 1$. Hence, we have:

$$\left( \frac{\log x}{\theta a \log L} \right)^{-\frac{\log x}{\theta a \log L}} \le u(n)^{-u(n)}. \quad (3.5)$$

From (3.4) and (3.5) we obtain (ii).□

Now we have the main result:

**Theorem 6** Let $0 < c, \theta < 1$ and $n \in \mathbb{N}$ and define $M_{ble}$ and $M_{ed}$ as above. Then:

$$(i) \ #M_{ble} \le n \cdot L_n\left(\frac{1}{3}, -\frac{c}{3\theta a}\right)^{1+o(1)};$$

$$(ii) \ #M_{ed} \ge n \cdot L_n\left(\frac{1}{3}, -\frac{c}{3\theta a} - \frac{1-c}{3a}\right)^{1+o(1)}.$$

*proof*: (i) Since each element of $M_{ble}$ is uniquely written as a product of an element $t$ in $T(n^{1-c}, n^{1-c}, L^{\theta a})$ and one in $T(\frac{n}{t}, L^{\theta a}, 1)$, we have:

$$\#M_{ble} = \sum_{t \in T(n^{1-c}, n^{1-c}, L^{\theta a})} \psi\left(\frac{n}{t}, L^{\theta a}, 1\right), \quad (3.6)$$

or, equivalently:

$$\#M_{ble} = \sum_{t \in T(n^{1-c}, n^{1-c}, L^{\theta a})} \frac{n}{t} P_{\text{smooth}}\left(\frac{n}{t}, L^{\theta a}, 1\right) \quad (3.7)$$

For all $t \in T(n^{1-c}, n^{1-c}, L^{\theta a})$, we have $\frac{n}{t} \in [n^c, n]$. From lemma 3 we know:

$$P_{\text{smooth}}\left(\frac{n}{t}, L^{\theta a}, 1\right) \le u(n)^{-u(n)(1-\bar{\epsilon}(n))}.$$

When inserting in (3.7), we obtain:

$$\#M_{ble} \le n \cdot u(n)^{-u(n)(1+\bar{\epsilon}(n))} \cdot \sum_{T(n^{1-c}, n^{1-c}, L^{\theta a})} \frac{1}{t}. \quad (3.8)$$
On one hand corollary 2 gives $u(n)^{u(n)} = L_n(\frac{1}{3}, \frac{c}{3\theta a})$. On the other hand $\Sigma_{T(n^{1-c},n^{1-c},L^{\theta a})} \frac{1}{t}$ is dominated by $\Sigma_{t=1}^n \frac{1}{t} \le \log n + 1$. When injecting in (3.8), we find:

$$ \#M_{ble} \le n \cdot L_n(\frac{1}{3}, -\frac{c}{3\theta a})^{1+o(1)} \cdot (\log n + 1) = n \cdot L_n(\frac{1}{3}, -\frac{c}{3\theta a})^{1+o(1)}. \quad (3.9) $$

(ii) By splitting $M_{ed}$ on the non smooth factor of each element, in the same way we obtained (3.6), we get:

$$ \#M_{ed} = \sum_{t \in T(n^{1-c}, L^a, L^{\theta a})} \psi(\frac{n}{t}, L^{\theta a}, 1). \quad (3.10) $$

For $t \le n^{1-c}$ we have $\frac{n}{t} \ge n^c$ and therefore $\psi(\frac{n}{t}, L^{\theta a}, 1) = \#T(\frac{n}{t}, L^{\theta a}, 1) \ge \#T(n^c, L^{\theta a}, 1) = \psi(n^c, L^{\theta a}, 1)$. When inserting in (3.10), we have:

$$ \#M_{ed} \ge \sum_{t \in T(n^{1-c}, L^a, L^{\theta a})} \psi(n^c, L^{\theta a}, 1). $$

The right side equals $\psi(n^{1-c}, L^a, L^{\theta a}) \cdot \psi(n^c, L^{\theta a}, 1)$. Finally, by corollary 2 we obtain:

$$ \begin{aligned} \#M_{ed} &\ge n^c L_n(\frac{1}{3}, -\frac{c}{3\theta a})^{1+o(1)} n^{(1-c)} L_n(\frac{1}{3}, -\frac{1-c}{3a})^{1+o(1)} = \\ &= n \cdot L_n(\frac{1}{3}, -\frac{c}{3\theta a} - \frac{1-c}{3a})^{1+o(1)}. \end{aligned} $$

□

**Time analysis** Since the candidates are generated by a perfect random generator, the average number of candidates we test before finding one in $M_{ed}$ is $\frac{n}{\#M_{ed}}$. Each candidate has the admissibility test, which takes time $t_{ECM}(L_n(\frac{2}{3}, \theta a)) = L_n(\frac{1}{3}, \sqrt{\frac{4}{3}\theta a})^{1+o(1)}(\log n)^2$ with $o(1)$ depending on $n$, not on the candidate. The average number of admissibles which will take the final test is $\frac{\#M_{ble}}{\#M_{ed}}$ because the admissibles are random. For each admissible, the final test takes time $t_{ECM}(L(\frac{2}{3}, a)) = L_n(\frac{1}{3}, \sqrt{\frac{4}{3}a})^{1+o(1)}$ with $o(1)$ independent on the admissible. Thus, the average time for the selection of one element in $M_{ed}$ is:

$$ t_{selection} = \frac{n}{\#M_{ed}} \cdot t_{ECM}(L_n(\frac{2}{3}, a\theta)) + \frac{\#M_{ble}}{\#M_{ed}} \cdot t_{ECM}(L_n(\frac{2}{3}, a)), $$

which according to theorem 6 is less than

$$ L_n(\frac{1}{3}, \frac{1-c}{3a} + \frac{c}{3\theta a} + \sqrt{\frac{4}{3}\theta a}) + L_n(\frac{1}{3}, \frac{1-c}{3a} + \sqrt{\frac{4}{3}a}). \quad (3.11) $$
For fixed a and c we minimize the time for $\theta = (\frac{c^2}{3a^3})^{\frac{1}{3}}$. We obtain the time:

$$L_n(\frac{1}{3}, \frac{1-c}{3a} + 3(\frac{c}{9})^{\frac{1}{3}}) + L_n(\frac{1}{3}, \frac{1-c}{3a} + \sqrt{\frac{4}{3}}a). \quad (3.12)$$

We minimize for $c = \frac{(\frac{4}{3}a)^{\frac{3}{2}}}{3}$. We obtain a function in a which reaches its minimum for $a = 0.7715$. It gives $c = 0.348$ and $\theta = 0.445$, which verify condition the $0 < \theta, c < 1$. We insert the numerical values in (3.11) and obtain:

$$time_{selection} = L_n(\frac{1}{3}, 1.296)^{1+o(1)}.$$

### 3.2.2 Early abort strategy

Encouraged by our success with one admissibility test, we can imagine a strategy with $k \ge 2$ admissibility tests in a row. Let $\theta_1, \dots, \theta_k, c_1, \dots, c_k \in (0, 1)$ be parameters such that $\theta_1 < \dots < \theta_k$ and $c_1 + \dots + c_k \le 1$. For convenience we put $\theta_0 = 0$. For $h = \overline{1}, k$, we say that a number $m$ succeeded the $h^{th}$ admissibility test if a $L^{\theta_h a}$ smoothness test on $m$ finds a divisor $m_h$ of $m$ such that $m_h \ge m^{c_h}$. Each candidate takes the first admissibility test. If it succeeds it goes on to the next admissibility test. If it fails we discard it and consider the next candidate.

Let now be more formal. For all integers $m \le n$ and all indices $i = \overline{1}, k$, we call $m_i$ the largest factor of $m$ which belongs to $T(n, L^{\theta_i a}, L^{\theta_{i-1} a})$.

**Notation 2** Put $M_{ble}^0 = [1, n] \cap \mathbb{N}$. For all $i = \overline{1}, k$ we put:

$$M_{ble}^i = \{m \in M_{ble}^{i-1} | m_i \ge n^{c_i}\}.$$

Also put:

$$M_{ed} = \{m \in M_{ble}^k | m \text{ is } L_n(\frac{2}{3}, a)\text{-smooth}\}.$$

A similar theorem to 6 holds.

**Theorem 7** With the notations above, we have:

$$(i) \text{ for all } h = \overline{1}, k, \#M_{ble}^h \le n \cdot L_n(\frac{1}{3}, -\frac{c_1}{3\theta_1 a} - \dots -\frac{c_h}{3\theta_h a})^{1+o(1)};$$

$$(ii) \#M_{ed} \ge n \cdot L_n(\frac{1}{3}, -\frac{c_1}{3\theta_1 a} - \dots -\frac{c_k}{3\theta_k a} - \frac{1-c_1-\dots-c_k}{3a})^{1+o(1)}.$$

Before giving the proof, we need to show two lemmas.
**Lemma 4** Let $N = N(n)$ be an integer which depends on $n$. Let $h \le k$. For $j = \overline{1, h}$, put $\epsilon_j = \frac{1-c_j}{N}$ and $\eta = \frac{1-(c_1+\dots+c_h)}{N}$. Then we have

$$ \#M_{ble}^h \le N \sum_{i,i_1,\dots,i_{h-1}} \psi(n^{c_h-i_1\epsilon_1-\dots-i_{h-1}\epsilon_{h-1}+(i+1)\eta}, L^{\theta_{h,a}}) \cdot n^{1-c_1-\dots-c_h-i\eta}. \quad (3.13) $$

$$ \psi(n^{c_1+(i_1+1)\epsilon_1}, L^{\theta_1 a}) \dots \psi(n^{c_{h-1}+(i_{h-1}+1)\epsilon_{h-1}}, L^{\theta_{h-1} a}). \square $$

where the indices $i, i_1, \dots, i_{h-1}$ run in $\{0, \dots, N-1\}^h$.

*proof:* We keep the notation $L = L_n(\frac{2}{3}, 1)$. We also make some new notations:

1. For all $j = \overline{1, h}$, $T^j = \{t \in T(n, L^{\theta_{j,a}}, L^{\theta_{j-1} a}) \mid n^{c_j} \le t\}$;

2. For all $i = \overline{0, N-1}$ and $j = \overline{1, h}$, $T_i^j = T(n, L^{\theta_{j,a}}, L^{\theta_{j-1} a}) \mid n^{c_j+i\epsilon_j} \le t \le n^{c_j+(i+1)\epsilon_j}$;

3. $C^h = \{t \in T(n, n, L^{\theta_{h,a}}) \mid t \le n^{1-c_1-\dots-c_h}\}$;

4. For all $i = \overline{0, N-1}$, $C_i^h = \{t \in T(n, n, L^{\theta_{h,a}}) \mid n^{1-(c_1+\dots+c_h)-(i+1)\eta} \le t \le n^{1-(c_1+\dots+c_h)-i\eta}\}$.

Each number $m$ in $M_{ble}^h$ is written in a unique way as $m = t_1 \dots t_h \cdot t$ with $t_j \in T^j$ for $j = \overline{1, h}$ and $t \in C^h$ such that $t_1 \dots t_h \cdot t \le n$. In order to choose an element $m \in M_{ble}^h$ we pick $t_1 \in T^1, \dots, t_{h-1} \in T^{h-1}$ and $t \in C^h$ and then $t_h$ in $T(\frac{n}{t_1 \dots t_{h-1} t}, L^{\theta_{h,a}}, L^{\theta_{h-1} a})$. Therefore, we have:

$$ \#M_{ble}^h = \sum_{t \in C^h} \sum_{t_1 \in T^1} \dots \sum_{t_{h-1} \in T^{h-1}} \psi(\frac{n}{t_1 \dots t_{h-1} t}, L^{\theta_{h,a}}, L^{\theta_{h-1} a}). $$

One easily checks that we have the following disjoint unions: $C^h = \bigsqcup_{i=0}^{N-1} C_i^h$ and, for all $j = \overline{1, h}$, $T^j = \bigsqcup_{i=0}^{N-1} T_i^j$. Therefore, we have:

$$ \#M_{ble}^h = \sum_{i,i_1,\dots,i_{h-1}} \sum_{t \in C_i^h, t_1 \in T_{i_1}^1, \dots, t_{h-1} \in T_{i_{h-1}}^{h-1}} \psi(\frac{n}{t_1 \dots t_{h-1} t}, L^{\theta_{h,a}}, L^{\theta_{h-1} a}) \quad (3.14) $$

where the indices $i, i_1, \dots, i_{h-1}$ run in $\{0, \dots, N-1\}^h$. By the definition of $T_i^j$, for all $j = \overline{1, h-1}$, all $i_j = \overline{0, N-1}$ and all $t_j \in T_{ij}^j$, we have $t_j \ge n^{c_j+i_j\epsilon_j}$. Also, for all $i = \overline{0, N-1}$ and all $t \in C_i^h$, we have $t \ge n^{1-(c_1+\dots+c_h)-(i+1)\eta}$. Therefore we have $\frac{n}{t_1 \dots t_{h-1} t} \le n^{c_h+(i+1)\eta-i_1\epsilon_1-\dots-i_{h-1}\epsilon_{h-1}}$. Hence, (3.14) implies:

$$ \#M_{ble}^h \le \sum_{i,i_1,\dots,i_{h-1}} \sum_{t \in C_i^h, t_1 \in T_{i_1}^1, \dots, t_{l-1} \in T_{i_{h-1}}^{h-1}} \psi(n^{c_h-i_1\epsilon_1-\dots-i_{h-1}\epsilon_{h-1}+(i+1)\eta}, L^{\theta_{h,a}}, L^{\theta_{h-1} a}). $$

The right side of the equation above equals

$$ \sum_{i,i_1,\dots,i_{h-1}} \#C_i^h \#T_{i_1}^1 \dots \#T_{i_{h-1}}^{h-1} \psi(n^{c_h-i_1\epsilon_1-\dots-i_{h-1}\epsilon_{h-1}+(i+1)\eta}, L^{\theta_{h,a}}, L^{\theta_{h-1} a}). $$
For all $i = 0, N-1$, we have $C_i^h \subset T(n^{1-c_1-\dots-c_h-i\eta}, n^{1-c_1-\dots-c_h-i\eta}, L^{\theta_h a})$. For all $j = 1, h-1$, for all $i_j = 0, N-1$, we have $T_{ij}^j \subset T(n^{c_j+(i_j+1)\epsilon_j}, L^{\theta_j a}, L^{\theta_{j-1} a})$. Therefore we obtain:

$$ \# M_{ble}^h \le \sum_{i, i_1, \dots, i_{l-1}} \qquad (3.15) $$

$$ \begin{aligned} & \psi(n^{c_h - i_1 \epsilon_1 - \dots - i_{h-1} \epsilon_{h-1} + (i+1)\eta}, L^{\theta_h a}, L^{\theta_{h-1} a}) \cdot \psi(n^{1-c_1 - \dots - c_h - i\eta}, n^{1-c_1 - \dots - c_h - i\eta}, L^{\theta_h a}) \\ & \cdot \psi(n^{c_1 + (i_1+1)\epsilon_1}, L^{\theta_1 a}, L^{\theta_{0} a}) \dots \psi(n^{c_{h-1} + (i_{h-1}+1)\epsilon_{h-1}}, L^{\theta_{h-1} a}, L^{\theta_{h-2} a}). \end{aligned} $$

Further we use the inequality $\psi(x, y, z) \le \psi(x, y)$ which holds for all $x, y, z$ and obtain:

$$ \# M_{ble}^h \le \sum_{i, i_1, \dots, i_{l-1}} \qquad (3.16) $$

$$ \begin{aligned} & \psi(n^{c_h - i_1 \epsilon_1 - \dots - i_{h-1} \epsilon_{h-1} + (i+1)\eta}, L^{\theta_h a}) \cdot \psi(n^{1-c_1 - \dots - c_h - i\eta}, n^{1-c_1 - \dots - c_h - i\eta}) \\ & \cdot \psi(n^{c_1 + (i_1+1)\epsilon_1}, L^{\theta_1 a}) \dots \psi(n^{c_{h-1} + (i_{h-1}+1)\epsilon_{h-1}}, L^{\theta_{h-1} a}). \end{aligned} $$

<figure><img src="image_9.png" /></figure>

**Notation 3** For all $i, i_1, \dots, i_{h-1}$ in $[0, N-1]$ we put:

$$ \begin{aligned} f(i, i_1, \dots, i_{h-1}) = & \psi(n^{c_h - i_1 \epsilon_1 - \dots - i_{h-1} \epsilon_{h-1} + (i+1)\eta}, L^{\theta_h a}) \cdot n^{1-c_1 - \dots - c_h - i\eta} \\ & \cdot \psi(n^{c_1 + (i_1+1)\epsilon_1}, L^{\theta_1 a}) \dots \psi(n^{c_{h-1} + (i_{h-1}+1)\epsilon_{h-1}}, L^{\theta_{h-1} a}). \end{aligned} $$

**Lemma 5** For all $i, i_1, \dots, i_{h-1}$:

$$ f(i, i_1, \dots, i_{h-1}) \le n^{\epsilon_1 + \dots + \epsilon_{h-1} + \eta} \cdot \left( n \cdot L_n \left( \frac{1}{3}, -\frac{c_1}{3\theta_1 a} - \dots - \frac{c_h}{3\theta_h a} \right)^{1+o(1)} \right) $$

with $o(1)$ a function of $n$, independent on $N, i, i_1, \dots, i_{h-1}$, which tends to 0.

*proof:* Put $\tau = \frac{\theta_{h-1}}{\theta_h} = \frac{\max\{\theta_j | j \le h-1\}}{\theta_h}$. Since $0 < \theta_1 < \dots < \theta_k$ we have $0 < \tau < 1$. We distinguish two cases depending on the condition $\epsilon_1 i_1 + \dots + \epsilon_{h-1} i_{h-1} - i\eta \le \tau c_h$.

Let $0 \le i, i_1, \dots, i_{h-1} \le N-1$ be such that $\epsilon_1 i_1 + \dots + \epsilon_{h-1} i_{h-1} - i\eta \le \tau c_h$. Since $\tau < 1$ we have $c_h - i_1 \epsilon_1 - \dots - i_{h-1} \epsilon_{h-1} + i\eta \ge (1-\tau)c_h > 0$ and we can apply corollary 2 for all $\psi$ expressions in $f(i, i_1, \dots, i_{h-1})$. We obtain:

$$ f(i, i_1, \dots, i_{h-1}) \le n^{\epsilon_1 + \dots + \epsilon_{h-1} + \eta}. $$

$$ \cdot n \cdot L \left( \frac{1}{3}, -\frac{c_1 + i_1 \epsilon_1}{3\theta_1 a} - \dots - \frac{c_{h-1} + i_{h-1} \epsilon_{h-1}}{3\theta_{h-1} a} - \frac{c_h - i_1 \epsilon_1 - \dots - i_{h-1} \epsilon_{h-1} + i\eta}{3\theta_h a} \right)^{1+o(1)}. $$

where $o(1)$ is a function depending exclusively on $n$ and which tends to 0.
Let now $0 \le i, i_1, \dots, i_{h-1} \le N-1$ be such that $\epsilon_1 i_1 + \dots + \epsilon_{h-1} i_{h-1} - i\eta > \tau c_h$.
In particular we have $\epsilon_1(i_1+1) + \dots + \epsilon_{h-1}(i_{h-1}+1) > \tau c_h$. By dividing through
$$ \frac{\max\{\theta_j | j \le h-1\}}{\theta_h} $$

$$ \frac{1}{\max\{\theta_j | j < h\}} [(i_1 + 1)\epsilon_1 + \dots + (i_{h-1} + 1)\epsilon_{h-1}] > \frac{c_h}{\theta_h}. $$

For all $j \le h - 1$, we have $\max\{\theta_l | l \le h - 1\} \ge \theta_j$, and therefore:

$$ \frac{(i_1 + 1)\epsilon_1}{\theta_1} + \dots + \frac{(i_{h-1} + 1)\epsilon_{h-1}}{\theta_{h-1}} > \frac{c_h}{\theta_h}, $$

which we divide through $3a$ to find:

$$ \frac{c_1 + (i_1 + 1)\epsilon_1}{3\theta_1 a} + \dots + \frac{c_{h-1} + (i_{h-1} + 1)\epsilon_{h-1}}{3\theta_{h-1} a} > \frac{c_1}{3\theta_1 a} + \dots + \frac{c_{h-1}}{3\theta_{h-1} a} + \frac{c_h}{3\theta_h a}. $$

By elevating $L_n(\frac{1}{3}, 1)^{-1}$ to each side of the above inequality, we obtain:

$$ \begin{aligned} & L_n(\frac{1}{3}, -\frac{c_1 + (i_1 + 1)\epsilon_1}{\theta_1 a}) \cdots L_n(\frac{1}{3}, -\frac{c_{l-1} + (i_{l-1} + 1)\epsilon_1}{\theta_{l-1} a}) \le (3.17) \\ & \le L_n(\frac{1}{3}, -\frac{c_1}{3\theta_1 a} - \dots - \frac{c_l}{3\theta_l a}). \end{aligned} $$

For each $j = \overline{1, h-1}$ and each $i_j = \overline{0, N-1}$, according to corollary 2, we have:

$$ \psi(n^{c_j+(i_j+1)\epsilon_j}, L_n(\frac{2}{3}, \theta_j a)) = n^{c_j+(i_j+1)\epsilon_j} \cdot L_n(\frac{1}{3}, -\frac{c_j+(i_j+1)\epsilon_j}{3\theta_j a})^{1+\delta_{i,j,n}} $$

where $\delta_{i,j,n}$ is a function which depends on $N$, $j$, $i_j$ and $n$ and which tends to 0 when $n$ goes to the infinity, uniformly on $N$ and $i_j$. For $j$ we have only $k$ possible values, with $k$ absolute constant, so we have:

$$ \psi(n^{c_j+(i_j+1)\epsilon_j}, L_n(\frac{2}{3}, \theta_j a)) \le n^{c_j+(i_j+1)\epsilon_j} \cdot L_n(\frac{1}{3}, -\frac{c_j+(i_j+1)\epsilon_j}{3\theta_j a})^{1+o(1)} \quad (3.18) $$

with $o(1)$ depending only on $n$. From (3.17) and (3.18), we have:

$$ \psi(n^{c_1+(i_1+1)\epsilon_1}, L^{\theta_1 a}) \dots \psi(n^{c_{h-1}+(i_{h-1}+1)\epsilon_{h-1}}, L^{\theta_{l-1} a}) \le n^{\sigma} L(\frac{1}{3}, -\frac{c_1}{3\theta_1 a} - \dots -\frac{c_h}{3\theta_h a})^{1+o(1)} \quad (3.19) $$

with $\sigma = c_1 + \dots + c_{h-1} + (i_1 + 1)\epsilon_1 + \dots + (i_{h-1} + 1)\epsilon_{h-1}$.

We obviously have:

$$ \psi(n^{c_h - i_1 \epsilon_1 - \dots - i_{h-1} \epsilon_{h-1} + (i+1)\eta}, L^{\theta_h a}) \le n^{c_h - i_1 \epsilon_1 - \dots - i_{h-1} \epsilon_{h-1} + (i+1)\eta}. \quad (3.20) $$
By combining (3.19) and (3.20), we obtain:

$$f(i, i_1, \dots, i_{h-1}) \le n^{\epsilon_1 + \dots + \epsilon_{h-1} + \eta} \cdot (n \cdot L_n \left( \frac{1}{3}, -\frac{c_1}{3\theta_1 a} - \dots - \frac{c_h}{3\theta_h a} \right)^{1+o(1)})$$

<figure><img src="image_10.png" /></figure>

**proof of theorem 7:** (i) Put $N = [(\log n)^2]$. Fix $h \le k$. From lemma 4, we have:

$$\# M_{ble}^h \le \sum_{i, i_1, \dots, i_{h-1}} f(i, i_1, \dots, i_{h-1}).$$

From lemma 5, we have:

$$f(i, i_1, \dots, i_{h-1}) \le n^{\epsilon_1 + \dots + \epsilon_{h-1} + \eta} \cdot (n \cdot L_n \left( \frac{1}{3}, -\frac{c_1}{3\theta_1 a} - \dots - \frac{c_h}{3\theta_h a} \right)^{1+o(1)})$$

with $o(1)$ a function of $n$, independent on $N$, $i$, $i_1, \dots, i_{h-1}$, which tends to 0. When combining these two equations, we obtain:

$$\# M_{ble}^h \le (N^h n^{\epsilon_1 + \dots + \epsilon_{h-1} + \eta}) \cdot n \cdot L \left( \frac{1}{3}, -\frac{c_1}{3\theta_1 a} - \dots - \frac{c_h}{3\theta_h a} \right)^{1+o(1)}.$$

Since $N = [(\log n)^2]$, we have $N^h = L^{o(1)}$ and

$$n^{\epsilon_1 + \dots + \epsilon_{h-1} + \eta} = \exp\left(\frac{[h - 2(c_1 + \dots + c_{h-1}) - c_h]\log n}{N}\right) = \exp(o(1)) = \mathcal{O}(1).$$

We conclude:

$$\# M_{ble}^h \le n \cdot L_n \left( \frac{1}{3}, -\frac{c_1}{3\theta_1 a} - \dots - \frac{c_h}{3\theta_h a} \right)^{1+o(1)}.$$

(ii) For $1 \le i \le k$, put $S_i = [n^{c_i}, n^{c_i} L^{\theta_i a}] \cap T(n^{c_i} L^{\theta_i a}, L^{\theta_i a}, L^{\theta_{i-1} a})$. The map $(m_1, \dots, m_k, t) \mapsto t_1 \dots t_k t$ is an injection from

$$S_1 \times \dots \times S_k \times T(n^{1-c_1-\dots-c_k} L^{-(\theta_1+\dots+\theta_k)a}, L^a, L^{\theta_k a})) \text{ to } M_{ed}.$$

Therefore, we have:

$$\# M_{ed} \ge \# S_1 \dots \# S_k \psi(n^{1-c_1-\dots-c_k} \cdot L^{-(\theta_1+\dots+\theta_k)a}, L^a, L^{\theta_k a}). \quad (3.21)$$

Consider the map

$$\lambda: T(n^{c_i}, L^{\theta_i a}, L^{\theta_{i-1} a}) \times (\Pi(L^{\theta_i a}) - \Pi(L^{\theta_{i-1} a})) \rightarrow T(n^{c_i} L^{\theta_i a}, L^{\theta_i a}, L^{\theta_{i-1} a}) \\ (m, \pi) \mapsto m \cdot \pi$$
Each element $w \in T(n^{c_i} L^{\theta_i a}, L^{\theta_i a}, L^{\theta_{i-1} a})$ equals $\lambda(m, \pi)$ only for pairs $(m, \pi)$ such that $\pi | w$. Since $w$ has less than $\log_2 w$ prime divisors, $w$ is taken at most $\log_2 n$ times by $\lambda$. Therefore, we obtain:

$$ \psi(n^{c_i} L^{\theta_i a}, L^{\theta_i a}, L^{\theta_{i-1} a}) \geq \frac{1}{\log n} \psi(n^{c_i}, L^{\theta_i a}, L^{\theta_{i-1} a}) \cdot (\pi(L^{\theta_i a}) - \Pi(L^{\theta_{i-1} a})). $$

Therefore, by the Prime number theorem, $\frac{\psi(n^{c_i} L^{\theta_i a}, L^{\theta_i a}, L^{\theta_{i-1} a})}{\psi(n^{c_i}, L^{\theta_i a}, L^{\theta_{i-1} a})}$ goes to infinity with $n$. In particular, for sufficiently large $n$, we have $\frac{\psi(n^{c_i} L^{\theta_i a}, L^{\theta_i a}, L^{\theta_{i-1} a})}{\psi(n^{c_i}, L^{\theta_i a}, L^{\theta_{i-1} a})} \geq 2$. Therefore, we have:

$$ \#S_i = \psi(n^{c_i} \cdot L^{\theta_i a}, L^{\theta_i a}, L^{\theta_{i-1} a}) - \psi(n^{c_i}, L^{\theta_i a}, L^{\theta_{i-1} a}) \geq (2-1)\psi(n^{c_i}, L^{\theta_i a}, L^{\theta_{i-1} a}). \quad (3.22) $$

From (3.21) and (3.22), we get:

$$ \#M_{ed} \geq (\Pi_{i=1}^{k} \psi(n^{c_i}, L^{\theta_i a}, L^{\theta_{i-1} a})) \psi(n^{1-c_1-\dots-c_k} \cdot L^{-(\theta_1+\dots+\theta_k)a}, L^a, L^{\theta_k a}). \quad (3.23) $$

A direct use of corollary 2 gives:

$$ \#M_{ed} \geq nL_n(\frac{1}{3}, -\frac{c_1}{3\theta_1 a} - \dots -\frac{c_k}{3\theta_k a} - \frac{1-c_1-\dots-c_k}{3a})^{1+o(1)}. \quad \square $$

**Time Analysis** In order to find one element in $M_{ed}$, we need to inspect in average $\frac{\#M_{ble}^k}{\#M_{ed}}$ elements in $\#M_{ble}^k$. For $h = \overline{k, 1}$, in order to find $\frac{\#M_{ble}^h}{\#M_{ed}}$ elements in $\#M_{ble}^h$, we need to inspect $\frac{\#M_{ble}^h}{\#M_{ed}} \cdot \frac{\#M_{ble}^{h-1}}{\#M_{ble}^h}$ elements in $M_{ble}^{h-1}$. Therefore, the average time is:

$$ \text{time}_{\text{selection}} = [\sum_{h=1}^{k} \frac{\#M_{ble}^{h-1}}{\#M_{ed}} t_{ECM}(L_n(\frac{2}{3}, \theta_h a))] + \frac{\#M_{ble}^{k}}{\#M_{ed}} t_{ECM}(L_n(\frac{2}{3}, a)). \quad (3.24) $$

Therefore we have $\text{time}_{\text{selection}} = L_n(\frac{1}{3}, \max\{f_1, \dots, f_{k+1}\})^{1+o(1)}$, where

$$ f_i = \frac{c_i}{3\theta_i a} + \dots + \frac{c_k}{3\theta_k a} + \frac{1 - c_1 - \dots - c_k}{3a} + \sqrt{\frac{4}{3}\theta_i a} $$

for $i = \overline{1, k}$ and $f_{k+1} = \frac{1-c_1-\dots-c_k}{3a} + \sqrt{\frac{4}{3}a}$. We put $\theta_{k+1} = 1$ since it unifies the definitions for $f_i$ with $i = \overline{1, k}$ and for $f_{k+1}$. For $\theta_{i+1}, \dots, \theta_{k+1}, c_{i+1}, \dots, c_k$ and $c_i$ fixed, we minimize $f_i$ by imposing a relation between $c_i$ and $\theta_i$:

$$ \theta_i = (\frac{c_i^2}{3a^3})^{\frac{1}{3}}. $$
For each $i \le k$, as soon as $\theta_{i+1}, \dots, \theta_{k+1}, c_{i+1}, \dots, c_k$ are fixed and $(\theta_i, c_i)$ satisfy the preceding relation, we impose $f_i = f_{i+1}$ by

$$c_i = 9(\frac{\omega}{3})^3 \text{ with } \omega = (\frac{4}{3}a\theta_{i+1})^{\frac{1}{2}}.$$

This allows us to compute in a row $c_k, \theta_k, \dots, c_1, \theta_1$. Hence we obtain the time for each value of $a$. Starting from the value of $a$ in the case $k = 1$ we slowly change $a$ in order to minimize the time.

Here is a table with the results we found. The first row presents the values for the version with no admissibility test from [CS06].

<table><thead><tr><th>k</th><th>a</th><th>time</th><th>(θ<sub>1</sub>, c<sub>1</sub>)</th><th>(θ<sub>2</sub>, c<sub>2</sub>)</th><th>(θ<sub>3</sub>, c<sub>2</sub>)</th><th>(θ<sub>4</sub>, c<sub>4</sub>)</th><th>(θ<sub>5</sub>, c<sub>5</sub>)</th><th>(θ<sub>6</sub>, c<sub>6</sub>)</th><th>(θ<sub>7</sub>, c<sub>7</sub>)</th></tr></thead><tbody><tr><td>0</td><td>0.693</td><td>1.442</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1</td><td>0.771</td><td>1.296</td><td>(0.444, 0.367)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td>0.799</td><td>1.251</td><td>(0.198, 0.109)</td><td>(0.444, 0.367)</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td>0.808</td><td>1.238</td><td>(0.088, 0.032)</td><td>(0.198, 0.109)</td><td>(0.444, 0.367)</td><td></td><td></td><td></td><td></td></tr><tr><td>4</td><td>0.811</td><td>1.234</td><td>(0.039, 0.010)</td><td>(0.088, 0.032)</td><td>(0.198, 0.109)</td><td>(0.444, 0.367)</td><td></td><td></td><td></td></tr><tr><td>5</td><td>0.811</td><td>1.233</td><td>(0.017, 0.003)</td><td>(0.039, 0.010)</td><td>(0.088, 0.032)</td><td>(0.198, 0.109)</td><td>(0.444, 0.367)</td><td></td><td></td></tr><tr><td>6</td><td>0.811</td><td>1.232</td><td>(0.008, 0.001)</td><td>(0.017, 0.003)</td><td>(0.039, 0.010)</td><td>(0.088, 0.032)</td><td>(0.198, 0.109)</td><td>(0.444, 0.367)</td><td></td></tr><tr><td>7</td><td>0.811</td><td>1.232</td><td>(0.003, 0.0002)</td><td>(0.008, 0.001)</td><td>(0.017, 0.003)</td><td>(0.039, 0.010)</td><td>(0.088, 0.032)</td><td>(0.198, 0.109)</td><td>(0.444, 0.367)</td></tr></tbody></table>

We conclude that a good choice is $a = 0.811$ and $k = 6$. In this case we have

$$time(\text{strategy}) = L_n(\frac{1}{3}, 2.232)^{1+o(1)}.$$

## 3.3 Complexity Analysis of the Discrete Logarithm Factory

In section "Factorization Factory" we computed the complexity for steps SIEVE and LINEAR ALGEBRA. Let's see in detail smoothing and DESCENT.

### 3.3.1 Smoothing

Let $C$ denote the smoothness bound in SMOOTHING. In order to prove that the choice in Discrete Logarithm Factory is optimal we consider the parameter $\theta > 0$ such that $C = L_p(\theta)$. An ECM test costs $L_p(\frac{\theta}{2})$ as pointed out in the smoothness section. Therefore the total time of the smoothness step is:

$$P_{\text{smooth}}(L_p(1), L_p(\theta))^{-1} \cdot L_p(\frac{\theta}{2}). \qquad (3.25)$$

This is minimal for $\theta = \frac{2}{3}$. Therefore we have to take as smoothness bound $C = L_p(\frac{2}{3}, a)$ with $a$ parameter. According to subsection ?? a good choice is $a = 0.811$. We obtain:

$$time(\text{smoothing}) = L_p(\frac{1}{3}, 1.232)^{1+o(1)}.$$
**Remark 3** The smoothing step does not depend on the other steps and we will check that it is the dominant step in the individual logarithm part.

### 3.3.2 Descent

As announced in 2.10 we provide the full details for the descent by special $Q$. We reduce a number $Q$ of size $L_p(\frac{2}{3}, c)$ with $c$ a parameter chose at the smoothing step, for example $c = 0.811$ for the early abort strategy. Hence the complexity of the descent depends on $c$. Other global parameters which affect the time of the descent are $\beta$, such that the rational smoothness bound is $B_1 = L_p(\frac{1}{3}, \beta)$, $\gamma$, such that $B_2$ the algebraic bound is $B_2 = L_p(\frac{1}{3}, \gamma)$ and the number $V$ of number fields we use on the algebraic side. This is 1 in the case of the Discrete Logarithm Factory, but $V$ with $V = [L_p(\frac{1}{3}, \beta - \gamma)]$ for the algorithm of Commeine and Semaev that we are going to speed up. Also remember that $m$ is a root if $f$ in $\mathbb{F}_p$ and that $\alpha_j$ is a complex root of $f + j(X - m)$ in Commeine and Semaev's algorithm.

The algorithm uses different procedures depending on the nature of the input: a number or an ideal. Each procedure chooses its parameters depending on the size of the input: the absolute value, respectively norm, larger or smaller than $L_p(\frac{1}{2}, c_M)$, respectively $L_p(\frac{1}{2}, \overline{c_M})$. Finally the descent brings some more parameters: $e_i$, $\bar{e}_i$, $\nu_i$ and $\bar{\nu}_i$ for $i = 1, 2$. The parameters $e_i$ and $\bar{e}_i$ decide the size of the sieving domain in special $Q$ while $\nu_i$ and $\bar{\nu}_i$ describe how much we want to descend in one step. For intuition, notice that $i = 1$ suggests a parameter for the rational side while $i = 2$ for the algebraic one. Also an over-lined parameter has the same task as a simple parameter, but it refers to the descent of an ideal rather than a number.

**INPUT:** a number $Q$ or an ideal $\mathfrak{u}$ of size($\text{norm}$) less than $L_p(\frac{2}{3}, c)$, $q$ prime factor of $p-1$;

**OUTPUT:** $\log_T Q \bmod q$.

**Algorithm 3** Descent by special $Q$

1. **if** the input is a number **then** run procedure NUMBER **else** run procedure IDEAL **endif**.

2. procedure NUMBER($l$):

(a) **if** $|l| < L_p(\frac{1}{2}, c_M)$ **then** $\nu = \nu_1$ **else** $\nu = \nu_2$; **endif**.

(b) search a pair $(a, b)$ such that:

(i) $|a|, |b| \le L_p(\frac{1}{3}, e) \cdot |l|^{\frac{1}{2}}$ and $\text{gcd}(a, b) = 1$;

(ii) $l$ $| a - bm$ and $\frac{a-bm}{l}$ is $l^\nu$-smooth;
(iii) for some $1 \le j \le V$ ($a - b\alpha_j$) is $|l|^\nu$-smooth;

(c) apply procedure NUMBER to all prime factors of $a - bm$ and procedure IDEAL to all prime ideal factors of $(a - b\alpha_j)$;

(d) regroup the relations of the factors to obtain a relation for $l$.

### 3. procedure IDEAL(u):

(a) $n = N(u)$; **if** $n < L_p(\frac{1}{2}, c_M)$ **then** $\bar{\nu} = \bar{\nu}_1$ **else** $\bar{\nu} = \bar{\nu}_2$; **endif**

(b) search a pair $(a, b)$ such that

(i) $|a|, |b| \le L_p(\frac{1}{3}, \bar{e}) \cdot n^{\frac{1}{2}}$ and $\gcd(a, b) = 1$;

(ii) $(a - b\alpha_j) \cdot \mathbf{u}^{-1}$ is $n^{\bar{\nu}}$-smooth, where $j$ is such that $\mathbf{u} \subset K_j$;

(iii) $a - b\alpha_j \in u$ and $(a - b\alpha_j)$ is $n^{\bar{\nu}}$-smooth;

(c) apply algorithm 3 to all prime factors of $a - bm$ and $a - b\alpha_j$.

(d) regroup the relations of the factors to obtain a relation for $\mathbf{u}$.

**Complexity Analysis** Since the descent algorithm is a divide and conquer one, the total time is:

$$ (\text{number of calls of Algorithm 3}) \cdot \text{time(Algorithm 3)}. $$

We will show that the number of calls of Algorithm 3 is $e^{O((\log \log p)^2)}$ and $\text{time(Algorithm 3)}$ is $L_p(\frac{1}{3}, 1.188)^{1+o(1)}$ for Discrete logarithm Factory and $L_p(\frac{1}{3}, 1.134)^{1+o(1)}$ for the algorithm of Commeine and Semaev. Therefore

$$ \text{time(Descent Step)} = L_p(\frac{1}{3}, 1.188)^{1+o(1)}. $$

**Number of Applications of Algorithm 3** We reduce a number of size $L(\frac{2}{3})$ into numbers and ideals of size $L(\frac{1}{3})$. We are computing the number of knots of a tree of height $w$ and where each knot has at most $Z$ sons. Since $Z$ is the number of (rational and algebraic) divisors of a number or ideal of norm less than $p$ and since all numbers and ideals have the norm at least 2, we have $Z \le 2 \cdot \log_2 p = O(e^{\log \log p})$. For $w$ one picks the smallest value such that: $L_p(\frac{1}{3})^{\nu_i^w} \ge L_p(\frac{2}{3})$ and $L_p(\frac{1}{3})^{\bar{\nu}_i^w} \ge L_p(\frac{2}{3})$ for $i = 1, 2$. Hence we have: $w = \frac{\log(\log L_p(\frac{2}{3})/\log L_p(\frac{1}{3}))}{\min(\nu_1, \nu_2, \bar{\nu}_1, \bar{\nu}_2)} = O(\log(\log^\frac{1}{3} p)) = O(\log \log p)$. Therefore, the number of calls is: $\frac{Z^w - 1}{Z - 1} < Z^w = O(e^{\log \log p})O(\log \log p) = e^{O((\log \log p)^2)}$. $\square$
Time(Algorithm 3)

case $\nu_1 \quad |l| < L(\frac{1}{2}, c_M)$

Let's call $P_{1Q} = Prob((a - bm)$ is $|l|^{\nu_2} - smooth)$. By the computations below $P_{1Q} = L(\frac{1}{3}, -\frac{1}{3\delta\beta\nu_1})$. Let's put $P_{1A} = Prob((a - b\alpha)$ is $|l|^{\nu_2})$. We show below that $P_{1A} = L(\frac{1}{3}, -(\frac{\delta}{6\nu_1} + \frac{1}{3\delta\nu_1\beta} + \frac{e_1\delta}{3\nu_1\beta}))$. The total sieve space has approximately $\frac{(L(\frac{1}{3},e_1)|l|^{\frac{1}{2}})^2}{|l|}$ elements because we are only using the pairs $(a,b)$ in a square of $\mathbb{Z} \times \mathbb{Z}$ which belong to a lattice of volume $|l|$. Thus the sieve space is $L(\frac{1}{3}, 2e_1)$. The search of $(a,b)$ succeeds if $L(\frac{1}{3}, 2e_1) \cdot P_{1Q} \cdot (VP_{1A}) \ge 1$ where $V$ is the number of fields we use. This comes to $2e_1 \ge (\frac{1}{3\delta\beta\nu_1}) + [(\frac{\delta}{6\nu_1} + \frac{1}{3\delta\nu_1\beta} + \frac{e_1\delta}{3\nu_1\beta}) - (\beta - \gamma)]$. We fulfill this condition by taking $e_1 = (\frac{3\nu_1\beta}{6\nu_1\beta-\delta})(\frac{2}{3\nu_1\delta\beta} + \frac{\delta}{6\nu_1} - \beta + \gamma)$. We do the search by testing with ECM the smoothness of a number, then for every good pair $(a,b)$ we search by ECM a $j$ such that $(a - b\alpha_j)$ is smooth. There are $L(\frac{1}{3}, 2e_1)$ tests over $\mathbb{Q}$ and $\frac{1}{VP_{1A}}$ tests over the fields. The time of an ECM test is the same for both rational and algebraic side: $L(|l|^{\nu_1})(\frac{1}{2}, \sqrt{2}) = L(\frac{1}{4})$. Therefore, the time-cost of this case is: $t_1 = L(\frac{1}{4}) \cdot (L(\frac{1}{3}, 2e_1) + V^{-1}P_{1A}^{-1}) = L(\frac{1}{3}, \max(2e_1, ((\frac{\delta}{6\nu_1} + \frac{1}{3\delta\nu_1\beta} + \frac{e_1\delta}{3\nu_1\beta}) - (\beta - \gamma))))$. This is $L(\frac{1}{3}, 2e_1))$ by the choice of $e_1$. Now $\nu_1 \mapsto e_1(\nu_1)$ is a function onto $\mathbb{R}_+$ using the formula $\nu_1 = \frac{4+\beta\delta^2+(2e_1)\delta^2}{6\delta\beta(\beta-\gamma+(2e_1))}$. The only problem is that $\nu_1$ might be outside $(0,1)$. We try to put $e_1 = \frac{c_r}{2}$ where the time for case $\nu_2$ is $t_2 = L(\frac{1}{3}, c_r)$. If $\nu_1 \ge 1$ we increase $e_1$ gradually.

case $\nu_2 \quad |l| \ge L(\frac{1}{2}, c_M)$

Let's call $P_{2Q} = Prob((a - bm)$ is $|l|^{\nu_2} - smooth)$. By the computations below $P_{2Q} = L(\frac{1}{6})$. Let's put $P_{2A} = Prob((a - b\alpha)$ is $|l|^{\nu_2})$. We show below that $P_{2A} = L(\frac{1}{3}, -\frac{\delta}{6\nu_2})$. The search of $(a,b)$ succeeds if $L(\frac{1}{3}, 2e_2) \cdot P_{2Q} \cdot (VP_{2A}) \ge 1$ where $V$ is the number of fields we use. It comes to $e_2 \ge \frac{1}{2}(\gamma - \beta + \frac{\delta}{6\nu_2})$. We fulfill this condition by taking $e_2 = \frac{1}{2}(\gamma - \beta + \frac{\delta}{6\nu_2})$. Similarly to the case $\nu_1$ the time-cost is: $t_2 = time(a \text{ test ECM}) \cdot (L(\frac{1}{3}, 2e_2) + \frac{1}{VP_{2A}})$. A test ECM takes more time here because the smoothness bound is larger: $L(|l|^{\nu_2})(\frac{1}{2}, \sqrt{2}) = L(\frac{1}{3}, 2 \cdot 3^{-\frac{2}{3}}\sqrt{\nu_2})$. Therefore $t_2 = L(\frac{1}{3}, 2\sqrt{\frac{\nu_2 c}{3}}) \cdot [L(\frac{1}{3}, 2e_2) + L(\frac{1}{3}, \frac{\delta}{6\nu_2} - (\beta - \gamma))] = L(\frac{1}{3}, 2\sqrt{\frac{\nu_2 c}{3}}) \cdot 2L(\frac{1}{3}, 2e_2) = L(\frac{1}{3}, 2 \cdot 3^{-\frac{2}{3}}\sqrt{\nu_2} + \frac{\delta}{6\nu_2} - (\beta - \gamma))$. We minimize $t_2$ by taking $\nu_2 = (\frac{\delta^2}{12c})^{1/3}$.

case $\bar{\nu}_1 \quad N(\mathfrak{u}) < L(\frac{1}{2}, \bar{c}_M)$

Put as above $n = N(\mathfrak{u})$. Like while reducing a number put $\bar{P}_{1Q} = Prob((a - bm)$ is $n^{\bar{\nu}_1} - smooth)$ and $\bar{P}_{1A} = Prob((a - b\alpha)$ is $n^{\bar{\nu}_1}$). According to 1 we have $\bar{P}_{1Q} = L(\frac{1}{3}, -\frac{1}{3\delta\beta\bar{\nu}_1})$ and $\bar{P}_{1A} = L(\frac{1}{3}, \frac{\delta}{6\bar{\nu}_1} + \frac{1}{3\delta\bar{\nu}_1\beta} + \frac{e_1\delta}{3\bar{\nu}_1\beta})$. We do the search in the same way. What changes is that $(a - b\alpha_j)$ is
smooth exactly in the field $K_j$ which contains $\mathfrak{u}$. This changes the condition
into $L(\frac{1}{3}, 2\bar{e}_1) \cdot \bar{P}_{1Q} \cdot (\bar{P}_{1A}) \ge 1$. Hence $2\bar{e}_1 \ge (\frac{1}{3\delta\beta\bar{v}_1}) + [(\frac{\delta}{6\bar{v}_1} + \frac{1}{3\delta\bar{v}_1\beta} + \frac{\bar{e}_1\delta}{3\bar{v}_1\beta})]$.
As usual we take $\bar{e}_1 = (\frac{3\bar{v}_1\beta}{6\bar{v}_1\beta-\delta})(\frac{2}{3\bar{v}_1\delta\beta} + \frac{\delta}{6\bar{v}_1})$. The time-cost of a ECM test
here doesn't change with respect to case $\nu_1$ because the smoothness bound
is the same. Now we can compute the time-cost: $\bar{t}_1 = L(\frac{1}{3}, 2\bar{e}_1) + \bar{P}_{1A}^{-1} =
L(\frac{1}{3}, \max(2\bar{e}_1, \frac{1}{3\delta\bar{v}_1\beta} + \frac{\delta\bar{e}_1}{\bar{v}_1\beta})) = L(\frac{1}{3}, 2\bar{e}_1)$. Just like in the case $\nu_1$ we have
$\bar{v}_1 = \frac{4+\delta^2\gamma+\bar{e}_1\delta^2}{6\delta\gamma\bar{e}_1}$ with $\bar{e}_1 = \frac{c_r}{2}$ (with $c_r$ as above) or the smallest value which
gives a $\bar{v}_1$ in $(0, 1)$.

$$
\text{case } \bar{\nu}_2 \ N(\mathfrak{u}) \geq L(\frac{1}{2}, \bar{c}_M)
$$

Put as above $n = N(\mathfrak{u})$. We use $\bar{P}_{2Q} = L(\frac{1}{6})$ and $\bar{P}_{2A} = L(\frac{1}{3}, -\frac{\delta}{6\bar{\nu}_2})$.
The condition, same as in case $\bar{\nu}_1$, is fulfilled with $\bar{e}_2 = \frac{\delta}{6\bar{\nu}_2}$. An ECM
test takes time $L(n^{\bar{\nu}_2})(\frac{1}{2}, \sqrt{2})$. Since all the ideals to be reduced come from
the descent of some large $l$ we have $n \le L(\frac{2}{3}, c)^{\nu_2}$. Therefore ECM takes
time $L(\frac{1}{3}, 2\sqrt{\frac{\bar{\nu}_2\nu_2c}{3}})$. Hence we have: $\bar{t}_2 = L(\frac{1}{3}, 2\sqrt{\frac{\nu_2\bar{\nu}_2c}{3}})(L(\frac{1}{6}) + L(\frac{1}{3}, \frac{\delta}{6\bar{\nu}_2}))$
$= L(\frac{1}{3}, \frac{\delta}{6\bar{\nu}_2} + 2\sqrt{\frac{\nu_2\bar{\nu}_2c}{3}})$. We minimize $\bar{t}_2$ for $\bar{\nu}_2 = (\frac{\delta^2}{12\nu_2c})^{\frac{1}{3}}$.

**Numerical Application** Using the information above we can compute the best values for the parameters as well as the complexity of the descents. We obtain time $L(\frac{1}{3}, 1.145)$ if one made steps 1 and 2 with parameters as in NFS, $L(\frac{1}{3}, 1.134)$ for the algorithm of Comm eine and Semaev and $L(\frac{1}{3}, 1.188)$ the Discrete Logarithm Factory. Notice that for the Discrete Logarithm Factory the descent is longer than in the normal case because we descent lower, i.e. $\beta$ is smaller. Despite a low smoothness bound, the descent is fast for Comm eine and Semaev's algorithm because the multiple fields help us to find relations during descent. The same computations allow us to find the complexity of the descent step for arbitrary values of $\beta$.

Computing the probabilities

$P_{1Q}$ We have: $\frac{|a+bm|}{l} = \frac{L(\frac{1}{3}, e_1)|l|^{\frac{1}{2}} L(\frac{2}{3}, \frac{1}{6})}{|l|} = L(\frac{2}{3}, \frac{1}{6})|l|^{-\frac{1}{2}}$. Further we have:

$P_{1Q} = P_{\text{smooth}}(L(\frac{2}{3}, \frac{1}{\delta})|l|^{-\frac{1}{2}}, |l|^{\nu_1}) = u^{-u}$ where $u = \frac{\log(L(\frac{2}{3}, \frac{1}{\delta})|l|^{-\frac{1}{2}})}{\nu_1 \log|l|} = -\frac{1}{2\nu_1} + \frac{\log L(\frac{2}{3}, \frac{1}{\delta})}{\nu_1 \log l}$. Since the map $u \mapsto u^{-u}$ is decreasing, the smallest, i. e. worst, probability occurs when $u = u_{max}$. At its turn $l \mapsto u(l)$ is decreasing, so $u_{max} = u(l_{min}) = u(L(\frac{1}{3}, \beta))$. Thus $u_{max} = (1+o(1))^{\frac{1}{\delta\nu_1\beta}}(\log p)^{\frac{1}{3}}(\log \log p)^{-\frac{1}{3}}$.
Therefore $P_{1Q} \ge (-\frac{1}{2\nu_1} + \frac{\log L(\frac{2}{3}, \frac{1}{\delta})}{\nu_1 \log L(\frac{1}{3}, \beta)})^{-\frac{1}{3}} \log \log p = L(\frac{1}{3}, -\frac{1}{3\delta\beta\nu_1})$.
$P_{1A}$ We have for all $j$: $N(a - b\alpha_j) \le dL(\frac{2}{3}, \frac{1}{\delta})(L(\frac{1}{3}, e_1)|l|^{\frac{1}{2}})^d = L(\frac{2}{3}, \frac{1}{\delta} + e_1\delta)|l|^{\frac{d}{2}}$.
Hence $\log N(a-b\alpha_j) = \log|l|^{\frac{\delta}{2}}(\log p)^{\frac{1}{3}}(\log \log p)^{-\frac{1}{3}} + (\frac{1}{\delta} + e_1\delta)(\log p)^{\frac{2}{3}}(\log \log p)^{\frac{1}{3}}$.
We also have $\log(|l|^{\nu_1}) = \nu_1 \log|l|$. Therefore $u = \frac{1}{\nu_1}(\frac{\delta}{2}(\log p)^{\frac{1}{3}}(\log \log p)^{-\frac{1}{3}} + \frac{1}{\log|l|}(\frac{1}{\delta} + e_1\delta)(\log p)^{\frac{2}{3}}(\log \log p)^{\frac{1}{3}})$. As before we use the maximum value of $u$
which is $u_{max} = \frac{1}{\nu_1}(\frac{\delta}{2}(\log p)^{\frac{1}{3}}(\log \log p)^{-\frac{1}{3}} + \frac{1}{\log L(\frac{1}{3},\beta)}(\frac{1}{\delta} + e_1\delta)(\log p)^{\frac{2}{3}}(\log \log p)^{\frac{1}{3}}) = L(\frac{1}{3}, \frac{\delta}{2\nu_1} + \frac{1}{\delta\nu_1\beta} + \frac{e_1\delta}{\nu_1\beta})$. Hence $\log u_{max} = (1+o(1))\frac{1}{3}\log p$. Which leads to
$P_{1A} \ge L(\frac{1}{3}, -(\frac{\delta}{6\nu_1} + \frac{1}{3\delta\nu_1\beta} + \frac{e_1\delta}{3\nu_1\beta}))$.

$P_{2Q}$ It is the probability that a number of size $L(\frac{2}{3})$ is $L(\frac{1}{2})$ - smooth because $n \ge L(\frac{1}{2})$. It is $L(\frac{1}{6})^{-1}$.

$P_{2A}$ The computations are the same as in case $P_{1A}$ until we compute $u$. Then
$u_{max} = \frac{1}{\nu_2}(\frac{\delta}{2}(\log p)^{\frac{1}{3}}(\log \log p)^{-\frac{1}{3}} + \frac{1}{\log L(\frac{1}{2},c_M)}(\frac{1}{\delta} + e_1\delta)\log^{\frac{2}{3}}p(\log \log p)^{\frac{1}{3}})$ be-
cause $l$ is larger. Thus $u_{max} = (1+o(1))\frac{\delta}{2\nu_2}(\log p)^{\frac{1}{3}}\log \log^{-\frac{1}{3}}p$. Hence
$\log u_{max} = (1+o(1))\frac{1}{3}\log p$ and $P_{2A} \ge L(\frac{1}{3}, -\frac{\delta}{6\nu_2})$.

$\bar{P}_{1Q}$ The difference with $P_{1Q}$ is that we have to replace $\nu$ by $\bar{\nu}$ and $e_1$ by $\bar{e}_1$, then to add $\frac{1}{\bar{\nu}_1}$ to $u$. Indeed we used to test for smoothness the number $\frac{a-bm}{l}$ while here we test $a - b\alpha_j$. Since $u \to \infty$, adding a constant doesn't change the result in a first approximation. Therefore $\bar{P}_{1Q} = L(\frac{1}{3}, -\frac{1}{3\delta\beta\bar{\nu}_1})$.

$\bar{P}_{1A}$ Instead of testing for smoothness $(a - b\alpha_j)$ as in $P_{1A}$, we test $(a - b\alpha_j) \cdot \mathbf{u}^{-1}$.
This changes the expected value of $u$ by subtracting $\frac{1}{\bar{\nu}_1}$. It doesn't change
the result, so $\bar{P}_{1A} = L(\frac{1}{3}, \frac{\delta}{6\bar{\nu}_1} + \frac{1}{3\delta\bar{\nu}_1\beta} + \frac{e_1\delta}{3\bar{\nu}_1\beta})$.

$\bar{P}_{2Q}$ Just like in $P_{2Q}$, we have $\bar{P}_{2Q} = L(\frac{1}{6})^{-1}$.

$\bar{P}_{2A}$ The difference with the expected value of $u$ by analogy with $P_{2A}$ is that we have to subtract $O((\log p)^{\frac{1}{6}})$. It doesn't count because $u$ has size $(\log p)^{\frac{1}{3}}$. Thus $\bar{P}_{2A} = L(\frac{1}{3}, -\frac{\delta}{6\bar{\nu}_2})$.
# Chapter 4

# Conclusion and Perspectives

The present report pushes further a series of algorithms evolved from Index Calculus. On the one hand, we showed that the idea of Factorization Factory is not incompatible with the discrete logarithm problem. Thus we described a DLP algorithm called Discrete Logarithm Factory with complexity $L_p(\frac{1}{3}, 1.639)$. On the other hand we speeded up the fastest algorithm in practice by adapting the idea of early abort to the NFS family. It brings the complexity of individual logarithm to $L_p(\frac{1}{3}, 1.232)$ which can have consequences for DLP-based cryptosystems.

There are questions which remain open and further improvements which might happen in the field. Let us make a non exhaustive list:

1. Pushing the early abort strategy to its limits. Indeed, in our analysis we showed that 8 admissibility tests bring the complexity to $L_p(\frac{1}{3}, 1.232)^{1+o(1)}$. Can one adapt the number of tests to the size of $p$ in order to speed up the theoretical complexity?

2. Adapting the techniques of descent and early abort to other algorithms. Indeed the similarities between $\mathbb{F}_p$ and $\mathbb{F}_{p^n}$ might lead to similar algorithms.

3. Improving the polynomial selection. Indeed, the difference of complexity between NFS and the Special Number Field Sieve (SNFS) is a consequence of the fact that in the SNFS the coefficients of the polynomial are in $O(1)$. Despite a negative result in [BLP93] which showed that there are values of $p$ where no improvements can be made, we ignore the existence of a better choice of the polynomials which could speed up NFS on average or for a non negligible fraction of inputs.
Bibliography

[Adl08] L. Adleman. A subexponential algorithm for the discrete logarithm problem with applications to cryptography. In *Foundations of Computer Science, 1979., 20th Annual Symposium on*, pages 55–60. IEEE, 2008.

[Bac84] E. Bach. Discrete logarithms and factoring. Technical Report CSD-84-186, University of California at Berkley, 1984.

[BLP93] J.P Buhler, H.W. Lenstra, and C. Pomerance. Factoring integers with the number field sieve. In A.K Lenstra and H.W. lenstra (eds), *The development of the Number Field Sieve*, volume 1554 of *Lecture Notes in Mathematics*, pages 50–94. Springer-Verlang, 1993.

[Bou70] V. Bouniakowsky. –. *Bulletin of the Academy of Science in Sankt Petersburg*, 1870.

[CEP83] E. Canfield, P. Erdös, and C. Pomerance. On a problem of oppenheim concerning "factorisation numerorum". *Journal of Number Theory*, 17:1–28, 1983.

[CL84] H. Cohen and H. Lenstra. Heuristics on class groups of number fields. *Number Theory Noordwijkerhout 1983*, pages 33–62, 1984.

[Coh93] H. Cohen. *A Course in Computational Algebraic Number Theory*. Springer-Verlang, 1993.

[Cop93] D. Coppersmith. Modifications to the number field sieve. *J. of Cryptology*, 6:169–180, 1993.

[Cop02] D. Coppersmith. Fast evaluation of logarithms in fields of characteristic two. *Information Theory, IEEE Transactions on*, 30(4):587–594, 2002.

[COS86] D. Coppersmith, AM Odlyzko, and R. Schroeppel. Discrete logarithms in GF (p), *Algorithmica*. Vol, 1:1–15, 1986.
[CS06] An Commeine and Igor Semaev. An algorithm to solve the discrete logarithm problem with the number field sieve. In *Public Key Cryptography*, pages 174–190, 2006.

[CW08] D. Coppersmith and S. Winograd. On the asymptotic complexity of matrix multiplication. In *Foundations of Computer Science, 1981. 22nd Annual Symposium on*, pages 82–90. IEEE, 2008.

[DH76] W. Diffie and M. Hellman. New directions in cryptography. *IEEE Transactions on Information Theory*, 22(6):644–654, 1976.

[ElG02] T. ElGamal. A subexponential-time algorithm for computing discrete logarithms over $GF(p^2)$. *Information Theory, IEEE Transactions on*, 31(4):473–481, 2002.

[Gor93] D. Gordon. Discrete logarithms in $gf(p)$ using the number field sieve. *SIAM Journal of Discrete Mathematics*, 6:124–138, 1993.

[JL03] A. Joux and R. Lercier. Improvements to the general number field for discrete logarithms in prime fields. *Mathematics of Computation*, 72:953–967, 2003.

[Kra22] M. Kraïtchik. *Théorie des nombres*. Gauthier-Villars, 1922.

[Len87] H.W. Lenstra. Factoring integers with elliptic curves. *Annals of mathematics*, 126(3):649–673, 1987.

[PH78] S. Pohlig and M. Hellman. An improved algorithm for computing logarithms over $GF(p)$ and its cryptographic significance. *IEEE Trans. Inform. Theory*, IT-24:106–110, 1978.

[Poh77] S. C. Pohling. Algebraic and combinatoric aspects of cryptography. Technical report, Stanford University, October 1977.

[Pol93] J. Pollard. The lattice sieve. *The development of the number field sieve*, pages 43–49, 1993.

[Pom82] C. Pomerance. Analysis and comparison of some integer factoring algorithms. *Mathematisch Centrum Computational Methods in Number Theory*, Pt. 1 p 89-139(SEE N 84-17990 08-67), 1982.

[Pom08] C. Pomerance. A tale of two sieves. *Biscuits of Number Theory*, page 85, 2008.
[Sch93] O. Schirokauer. Discrete logarithms and local units. *Philosophical Transactions of the Royal Society London, series A*, 345:409-424, 1993.

[Sch05] O. Schirokauer. Virtual logarithms. *Journal of Algorithms*, 57:140–147, 2005.

[Sho90] V. Shoup. Searching for primitive roots in finite fields. In *Proceedings of the twenty-second annual ACM symposium on Theory of computing*, pages 546–554. ACM, 1990.

[Sho09] V. Shoup. *A computational introduction to number theory and algebra*. Cambridge University Press, 2009.

[Sil87] R.D. Silverman. The multiple polynomial quadratic sieve. *Mathematics of Computation*, 48(177):329–339, 1987.

[Sta07] HM Stark. The Gauss Class-Number Problems. *Analytic number theory: a tribute to Gauss and Dirichlet*, page 247, 2007.

[Wie86] D. H. Wiedemann. Solving sparse linear equations over finite fields. *IEEE Trans. Inform. Theory*, IT-32(1):54–62, 1986.
# Appendix

Here is a diagram representing algorithms of the Number Field Sieve family. Each box contains the name of an algorithm followed by its complexity, its author and year of publication. The color code is red for factorization and blue for discrete logarithm. For DLP algorithms, when we write “*x*”, then *y*”, *x* denotes the time of the precomputations while *y* is the time of the individual logarithm. If the algorithm was presented earlier in a conference or announced by personal communication we include the year in parenthesis.

<figure><img src="image_11.png" /></figure>