1 and deg$_y \phi = \eta - 1), we have $\mathcal{N}_i(\phi) = \tilde{O}(\|\phi\|_{\infty}^{\eta \deg(f_i)} \|f_i\|_{\infty}^{\eta} \|h\|_{\infty}^{(\eta-1) \deg(f_i)})$ for all $i \ge 0$. More precisely, since $\|\phi\|_{\infty} \le A^{1/(2\eta)}$, we get $\mathcal{N}_0 = \tilde{O}(A^{\kappa}) = L_Q(2/3, c_A/c_{\kappa})$ and $\mathcal{N}_* = \tilde{O}(A^{\kappa/2} Q^{1/(2\kappa)}) = L_Q(2/3, c_A/(2c_{\kappa}) + c_{\kappa}/2)$. These expressions of $c_{\mathcal{N}_0}$ and $c_{\mathcal{N}_*}$ yield the following optimum:

$$c = \frac{1}{2} \left( \frac{2 + 2\sqrt{2}}{9} \right)^{\frac{2}{3}} \approx 0.69, \quad c_{\kappa} = 2\sqrt{c} \approx 1.66, \quad c_A = 2c\sqrt{2} \approx 1.94.$$

### A.3 The large characteristic case in Theorem 2 (case 1a)

We consider the polynomials given by the first approach of Joux-Pierrot, as in §3.3. Hence $\mathcal{N}_0 = \tilde{O}(A^{n/t}Q^{(t-1)/(n\lambda)})$ and $\mathcal{N}_* = \tilde{O}(A^{\lambda n/t} \log(n)^{\lambda(t-1)})$. Let $\lambda = 1/(c_{\lambda}n)(\log(Q)/\log(\log(Q)))^{1/3}$ with $c_{\lambda}$ a constant. The norm of the sieve elements are $\mathcal{N}_0 = L_Q(2/3, c_{\lambda})$ and $\mathcal{N}_* = L_Q(2/3, c_A/(2c_{\lambda}))$, since $\log(n)^{\lambda}$ is negligible compared to $L_Q(\alpha_p - 2/3)$, and $\alpha_p - 2/3 \le 1/3 < 2/3$. From Condition (7) we get $c_A = 2c + c_{\lambda}/(3c)$. Substituting $c_A$ in Condition (6), we get $c_{\lambda} \ge 6c^2/(18c^3 - 1)$. For a given value $c$, it is best to choose the smallest possible value of $c_{\lambda}$ in order to minimize $c_A$, hence $c_{\lambda}$ is set to $c_{\lambda} = 6c^2/(18c^3 - 1)$. Moreover, $c$ can be chosen close to zero. In return, $c_A$ grows to infinity as $c$ tends to zero. We choose $c$ to minimize $c_A$, and get

$$c = \left(\frac{1}{3}\right)^{1/3} \approx 0.69, \quad c_{\lambda} = \left(\frac{8}{9}\right)^{1/3} \approx 0.96, \quad c_A = 2\left(\frac{8}{9}\right)^{2/3} \approx 1.85.$$

### A.4 The medium characteristic case $1/3 < \alpha < 2/3$ in Theorem 2

SNFS Factory (case 2a). The polynomials are chosen with the second approach of the Joux-Pierrot method of §3.3. Hence $\mathcal{N}_0 = \tilde{O}(A^{\lambda n/t} \log(n)^{\lambda(t-1)})$ and $\mathcal{N}_* = \tilde{O}(A^{n/t}Q^{(t-1)/(n\lambda)})$. We set $t = \delta n(\log(Q)/\log(\log(Q)))^{-1/3+o(1)}$. The norm of the sieve elements are $\mathcal{N}_0 = L_Q(2/3, \lambda c_A/\delta)$, since $\log(n)^{\lambda(t-1)}$ is negligible compared to $L_Q(2/3)$, and $\mathcal{N}_* = L_Q(2/3, c_A/\delta + \delta/\lambda)$. A solution of the system is:

$$c \ge \tilde{c} = \left( \frac{\lambda + 4 + 2\sqrt{2\lambda + 4}}{9\lambda} \right)^{1/3}, \quad c_A = \frac{6c^2\delta}{3c\delta - \lambda}, \quad \delta = \frac{\lambda(9c^3 + 1) + \sqrt{-27\lambda c^3 + \lambda^2(81c^6 - 18c^3 + 1)}}{6c}.$$

When $\lambda \in \{2, 3\}$, we set $c = \tilde{c}$. However, when $\lambda \in \{4, 5\}$, only the relation collection and linear algebra steps of the *per-field* step can reach complexity $L_Q(1/3, \tilde{c})$. As we show in Appendix B, the individual logarithm step is unfortunately more expensive, and we need to take $c$ somewhat larger than $\tilde{c}$ in order to keep the individual logarithm step negligible. Table 8 shows the values taken for $c$ for various values of $\lambda$. The complexity of the *one-off* step is $L_Q(1/3, c_A)$, and the complexity of the *per-field* step is $L_Q(1/3, 2c)$.
from which the claimed results follow.

### A.2.2 TNFS Factory (case 3b).

We only consider the case where $\eta$ and $\kappa$ are coprime. The general case is similar. Let $\kappa = 1/c_\kappa(\log(Q)/\log\log(Q))^{1/3+o(1)}$ with $c_\kappa$ a constant. As $Q$ tends to infinity, $\kappa$ also tends to infinity, so that the constraint that $\kappa$ is an integer divisor of $n$ can be absorbed by the $o(1)$ in the exponent, provided of course that the input is such that $n$ has such a factor. The sieve is done over elements of the form $a(t)X - b(t) \in \mathcal{O}_{\mathcal{K}_h}[X]$ with $a(t)$ and $b(t)$ in $\mathbb{Z}[t]$ of degree at most $\eta - 1$. According to the norm bounds of §2.3 (with $\deg_x \phi = 1$ and $\deg_y \phi = \eta - 1$), we have $N_i(\phi) = \tilde{O}(\|\phi\|_{\infty}^{\eta \deg(f_i)} \|f_i\|_{\infty}^{\eta} \|h\|_{\infty}^{(\eta-1) \deg(f_i)})$ for all $i \ge 0$. More precisely, since $\|\phi\|_{\infty} \le A^{1/(2\eta)}$, we get $N_0 = \tilde{O}(A^{\kappa}) = L_Q(2/3, c_A/c_\kappa)$ and $N_* = \tilde{O}(A^{\kappa/2}Q^{1/(2\kappa)}) = L_Q(2/3, c_A/(2c_\kappa) + c_\kappa/2)$. These expressions of $c_{N_0}$ and $c_{N_*}$ yield the following optimum:

$$c = \frac{1}{2} \left( \frac{2 + 2\sqrt{2}}{9} \right)^{\frac{2}{3}} \approx 0.69, \quad c_{\kappa} = 2\sqrt{c} \approx 1.66, \quad c_A = 2c\sqrt{2} \approx 1.94.$$

### A.3 The large characteristic case in Theorem 2 (case 1a)

We consider the polynomials of the first approach of Joux-Pierrot, as in §3.3. Hence $N_0 = \tilde{O}(A^{n/t}Q^{(t-1)/(n\lambda)})$ and $N_* = \tilde{O}(A^{\lambda n/t} \log(n)^{\lambda(t-1)})$. Let

$$\lambda = 1/(c_{\lambda}n)(\log(Q)/\log\log(Q))^{1/3}$$

with $c_\lambda$ a constant. The norm of the sieve elements are $N_0 = L_Q(2/3, c_\lambda)$ and $N_* = L_Q(2/3, c_A/(2c_\lambda))$, since $\log(n)^\lambda$ is negligible compared to $L_Q(\alpha_p - 2/3)$, and $\alpha_p - 2/3 \le 1/3 < 2/3$. From Condition (7) we get $c_A = 2c + c_\lambda/(3c)$. Substituting $c_A$ in Condition (6), we get $c_\lambda \ge 6c^2/(18c^3 - 1)$. For a given value $c$, it is best to choose the smallest possible value of $c_\lambda$ in order to minimize $c_A$, hence $c_\lambda$ is set to $c_\lambda = 6c^2/(18c^3 - 1)$. Moreover, $c$ can be chosen close to zero. In return, $c_A$ grows to infinity as $c$ tends to zero. We choose $c$ to minimize $c_A$, and get

$$c = \left(\frac{1}{3}\right)^{1/3} \approx 0.69, \quad c_{\lambda} = \left(\frac{8}{9}\right)^{1/3} \approx 0.96, \quad c_A = 2\left(\frac{8}{9}\right)^{2/3} \approx 1.85.$$

### A.4 The medium characteristic case $1/3 < \alpha < 2/3$ in Theorem 2

#### A.4.1 SNFS Factory (case 2a).

The polynomials are chosen with the second approach of the Joux-Pierrot method of §3.3. Hence $N_0 = \tilde{O}(A^{\lambda n/t} \log(n)^{\lambda(t-1)})$ and $N_* = \tilde{O}(A^{n/t}Q^{(t-1)/(n\lambda)})$. We set $t = \delta n(\log(Q)/\log\log(Q))^{-1/3+o(1)}$. The norm of the sieve elements are $N_0 = L_Q(2/3, \lambda c_A/\delta)$, since $\log(n)^{\lambda(t-1)}$ is negligible compared to $L_Q(2/3)$, and $N_* = L_Q(2/3, c_A/\delta + \delta/\lambda)$. A solution of the system is:

$$c \ge \tilde{c} = \left( \frac{\lambda + 4 + 2\sqrt{2\lambda + 4}}{9\lambda} \right)^{1/3}, \qquad (11)$$

$$c_A = \frac{6c^2\delta}{3c\delta - \lambda},$$

$$\delta = \frac{\lambda(9c^3 + 1) + \sqrt{-27\lambda c^3 + \lambda^2(81c^6 - 18c^3 + 1)}}{6c}.$$
**STNFS Factory (case 2b).** The Special Tower Number Field Sieve targets medium characteristic finite fields with sparse characteristic *p*, and composite extension degree *n* = *κη*. Let *κ* = 1/c<sub>κ</sub>(log(*Q*)/log log(*Q*))<sup>1/3+o(1)</sup> for some constant c<sub>κ</sub> to be determined. Consider *p*<sub>*i*</sub> = *P*(*u*), where *P* is a polynomial of degree *λ* with small coefficients, and *u* ≈ *Q*<sup>1/(λn)</sup> an integer. Again we assume that *κ* and *η* are coprime. The polynomials are chosen with the second approach of the Joux-Pierrot method as in §3.3. The bound of §2.3 gives *N*<sub>0</sub> = Ō(*A*<sup>λκ/2</sup>log(*κ*)<sup>λ</sup>) = *L*<sub>Q</sub>(2/3, *λc*<sub>A</sub>/(2*c*<sub>κ</sub>)) and *N*<sub>*</sub> = Ō(*A*<sup>κ/2</sup>*Q*<sup>1/(λκ)</sup>) = *L*<sub>Q</sub>(2/3, *c*<sub>A</sub>/(2*c*<sub>κ</sub>) + *c*<sub>κ</sub>/λ). The solution of the system related to Equations (5), (6), and (7) is

$$c \ge \tilde{c} = \left( \frac{\lambda + 4 + 2\sqrt{2\lambda + 4}}{18\lambda} \right)^{1/3}, c_A = \frac{12c^2 c_\kappa}{6cc_\kappa - \lambda} \\ c_\kappa = \frac{\lambda(18c^3 + 1) + \sqrt{-144\lambda c^3 + \lambda^2(324c^6 - 36c^3 + 1)}}{12c}.$$

When $\lambda = 2$, we set $c = \tilde{c}$. However, when $\lambda \ge 3$, the situation is similar to SNFS Factory, and we need to take $c$ larger than $\tilde{c}$ in order to keep the individual logarithm step negligible (see Appendix B). Table 9 shows the values taken for $c$ for various values of $\lambda$. The complexity of the *one-off* step is $L_Q(1/3, c_A)$, and the complexity of the *per-field* step is $L_Q(1/3, 2c)$.

## B Complexity of the Individual Logarithm step

The individual logarithm step is the last one in NFS and its variants, and also the last one inside the *per-field* phase in Factory, coupled or not with other variants. We prove in this Appendix that the complexity of the *individual logarithm* step is negligible compared to the rest of the *per-field* step for all the variants we studied. Hence, the complexities given in Table 3 are indeed the complete asymptotic complexities of the *per-field* step. The individual logarithm step consists of two main steps: the smoothing and the descent step.

### B.1 Smoothing step

The smoothing step consists in reducing the computation of the discrete logarithm of the target to the discrete logarithm of another element that is $\tilde{B}$-smooth once lifted to one of the number fields, where $\tilde{B} = L_Q(2/3, c_{\tilde{B}}) > B$. The smoothing step was improved for finite fields of composite extension degree in [2, 22]. The following lemma recapitulates the complexity of the smoothing step for all Factory variants. This result implies that the smoothing step is negligible compared to the complexity of the *per-field*, for all Factory variants.

**Lemma 1.** In all NFS Factory variants, the running time of the smoothing step in $\mathbb{F}_{p^n}$ to output an element $\tilde{B}$-smooth is $L_{p^n}(1/3, C = 3^{1/3}(23/27)^{2/3})$, where $\tilde{B} = L_{p^n}(2/3, c_{\tilde{B}})$ with $c_{\tilde{B}} = (1/3)^{1/3}(27/23)^{2/3}$. The approximated values are: $C \approx 1.30$, and $c_{\tilde{B}} \approx 0.77$.

*Proof.* The lemma is a direct consequence of Corollary 6.4 and Corollary 6.5 in [22], where substituting *e* and *d* by 1 is valid for all our Factory variants. □
When $\lambda \in \{2, 3\}$, we set $c = \tilde{c}$. However, when $\lambda \in \{4, 5\}$, only the relation collection and linear algebra steps of the *per-field* step can reach complexity $L_Q(1/3, \tilde{c})$. As we show in Appendix B, the individual logarithm step is unfortunately more expensive, and we need to take $c$ somewhat larger than $\tilde{c}$ in order to keep the individual logarithm step negligible. Table 8 shows the values taken for $c$ for various values of $\lambda$. The complexity of the *one-off* step is $L_Q(1/3, c_A)$, and the complexity of the *per-field* step is $L_Q(1/3, 2c)$.

### A.4.2 STNFS Factory (case 2b).

The Special Tower variant targets medium characteristic finite fields of sparse characteristic $p$, and composite extension degree $n = \kappa\eta$. Let $\kappa = 1/c_\kappa(\log(Q)/\log\log(Q))^{1/3+o(1)}$ for some constant $c_\kappa$ to be determined. Consider $p_i = P(u)$, where $P$ is a polynomial of degree $\lambda$ with small coefficients, and $u \approx Q^{1/(\lambda n)}$ an integer. Again we assume that $\kappa$ and $\eta$ are coprime. The polynomials are chosen with the second approach of the Joux-Pierrot method as in §3.3. The bound of §2.3 gives $N_0 = \tilde{O}(A^{\lambda\kappa/2}\log(\kappa)^\lambda) = L_Q(2/3, \lambda c_A/(2c_\kappa))$ and $N_* = \tilde{O}(A^{\kappa/2}Q^{1/(\lambda\kappa)}) = L_Q(2/3, c_A/(2c_\kappa) + c_\kappa/\lambda)$. The solution of the system related to Equations (5), (6), and (7) is

$$ 
\begin{align} 
c \ge \tilde{c} &= \left( \frac{\lambda + 4 + 2\sqrt{2\lambda + 4}}{18\lambda} \right)^{1/3}, \tag{12} \\ 
c_A &= \frac{12c^2c_\kappa}{6cc_\kappa - \lambda}, \\ 
c_\kappa &= \frac{\lambda(18c^3 + 1) + \sqrt{-144\lambda c^3 + \lambda^2(324c^6 - 36c^3 + 1)}}{12c}. \nonumber 
\end{align} 
$$

When $\lambda = 2$, we set $c = \tilde{c}$. However, when $\lambda \ge 3$, the situation is similar to SNFS Factory, and we need to take $c$ larger than $\tilde{c}$ in order to keep the individual logarithm step negligible (see Appendix B). Table 9 shows the values taken for $c$ for various values of $\lambda$. The complexity of the *one-off* step is $L_Q(1/3, c_A)$, and the complexity of the *per-field* step is $L_Q(1/3, 2c)$.

## B Complexity of the Individual Logarithm step

The individual logarithm step is the last one in NFS and its variants, and also the last one inside the *per-field* phase in Factory, coupled or not with other variants. We prove in this Appendix that the complexity of the *individual logarithm* step is negligible compared to the rest of the *per-field* step for all the variants we studied. Hence, the complexities given in Table 3 are indeed the complete asymptotic complexities of the *per-field* step. The individual logarithm step consists of two main steps: the smoothing and the descent step.

### B.1 Smoothing step

The smoothing step consists in reducing the computation of the discrete logarithm of the target to the discrete logarithm of another element that is $\tilde{B}$-smooth once lifted to one of the number fields, where $\tilde{B} = L_Q(2/3, c_{\tilde{B}}) > B$. The smoothing step was improved for finite fields of composite extension degree in [Gui19, AAP23]. The following lemma recapitulates the complexity of the smoothing step for all Factory variants. This result implies that the smoothing step is negligible compared to the complexity of the *per-field*, for all Factory variants.

**Lemma 1.** In all NFS Factory variants, the running time of the smoothing step in $\mathbb{F}_{p^n}$ to output an element $\tilde{B}$-smooth is $L_{p^n}(1/3, C = 3^{1/3}(23/27)^{2/3})$, where $\tilde{B} = L_{p^n}(2/3, c_{\tilde{B}})$ with $c_{\tilde{B}} = (1/3)^{1/3}(27/23)^{2/3}$. The approximated values are: $C \approx 1.30$, and $c_{\tilde{B}} \approx 0.77$.
## B.2 Descent step

This paragraph is inspired from [3], where the descent step is presented for NFS Factory in prime finite fields. We adapt the idea to other characteristic sizes and to the different variants coupled with Factory.

After the smoothing step, the target is $\tilde{B}$-smooth with $\tilde{B} = L_Q(2/3, c_{\tilde{B}}) > B$, where $c_{\tilde{B}}$ is as in Lemma 1. Thanks to the previous steps, we know the virtual logarithms of the prime ideals in $O_{K_0}$ that are both factors of the target and of norm below $B$. It remains to compute the virtual logarithms of those of norm between $B$ and $\tilde{B}$. Let $\mathbf{q}$ be such a prime ideal, of degree one and norm $q$. Define the special-$\mathbf{q}$ lattice $\mathcal{L}_{\mathbf{q}}$ of dimension $2\eta$ over $\mathbb{Z}$, and of determinant $q$, that corresponds to the elements $(a(\iota), b(\iota))$ such that the ideal $(a(\iota) - b(\iota)\alpha_0)$ is divisible by $\mathbf{q}$. Using the LLL algorithm, compute $(u_0, \dots, u_{2\eta-1})$ a basis of $\mathcal{L}_{\mathbf{q}}$ where $\|u_i\|_{\infty} = \tilde{O}(p^{1/(2\eta)})$ for $i = 0, \dots, 2\eta - 1$. Let $\xi \in (0, 1)$ a positive real number, to be determined later. The first step of the descent step consists in finding $(a(\iota), b(\iota)) \in \mathcal{L}_{\mathbf{q}}$ such that :

$$ - \frac{N_0(b(\iota) - a(\iota)\alpha_0)}{\mathbf{q}} \text{ is } \mathbf{q}^{\xi}\text{-smooth.} $$

$$ - \text{and } N_i(b(\iota) - a(\iota)\alpha_1) \text{ is } \mathbf{q}^{\xi}\text{-smooth.} $$

This permits to express the virtual logarithm of $\mathbf{q}$ as a linear combination of virtual logarithms of prime ideals of norm smaller than $\mathbf{q}^{\xi}$. To recover the virtual logarithm of $\mathbf{q}$, it is sufficient to repeat the process on each of the ideals in the linear combination until they are all in the factor basis.

We start by proving that the first step of the descent, i.e., finding $(a(\iota), b(\iota))$ as above, is the dominant step of the descent in terms of complexity. To descend the ideal $\mathbf{q}$ to the factor basis, we construct a tree where the root is $\mathbf{q}$ and the leaves are ideals in the factor basis. Each ideal that descends due to a pair $(a(\iota), b(\iota))$ introduces at most $\log_2(N_0(b(\iota) - a(\iota)\alpha_0) + \log_2(N_i(b(\iota) - a(\iota)\alpha_1))$ new nodes. By Corollary 6.4 in [22], both norms are smaller than $Q$. Hence, the arity of the tree is less than $2\log_2 Q$, and its depth is smaller than the smallest integer $k$ such that $\xi^k \log \tilde{B} \le \log B$. Hence, $k = O((\log \log Q))$. The number of nodes in the tree is less than $(2\log_2(Q))^k = \exp(O(\log \log(Q)^2))$. Denote $\mathcal{C}$ the complexity of the first descent of $\mathbf{q}$. We prove in the following paragraph that $\mathcal{C} = L_Q(1/3)$. Hence, the complexity of descending $\mathbf{q}$ to the factor basis is dominated by $\exp(O(\log \log(Q)^2)) \cdot \mathcal{C} = \mathcal{C}$. This process is applied on all the prime factors of the target that are not in the factor basis, their number is in $O(\log Q)$. In short, the complexity of the descent step is the complexity of descending $\mathbf{q}$, that is the complexity of finding $(a(\iota), b(\iota))$ as described above.

**Complexity of the descent step for NFS Factory and its variants.** For $\mu = (\mu_0, \dots, \mu_{2\eta-1})$ of infinity norm $S$, we look for “good” $(a(\iota), b(\iota))$ of the form $\mu_0 u_0 + \dots + \mu_{2\eta-1} u_{2\eta-1}$, either by sieving or ECM tests. Hence, $\|(a(\iota), b(\iota))\|_{\infty} = \tilde{O}(S q^{1/(2\eta)})$. We take $S^{2\eta} := L_Q(1/3, s)$ for a positive $s$ to be chosen. From the bound in §2.3, we get $N_i(a(\iota) - b(\iota)\alpha_i) = \tilde{O}((S^{2\eta})^{\deg(f_i)/2} \|f_i\|_{\infty}^{\eta} q^{\deg(f_i)/2})$, for $i = 0, 1$. We assume the two following usual heuristics. The probability of each
*Proof.* The lemma is a direct consequence of Corollary 6.4 and Corollary 6.5 in [Gui19], where substituting $e$ and $d$ by 1 is valid for all our Factory variants. □

## B.2 Descent step

This paragraph is inspired from [Bar13], where the descent step is presented for NFS Factory in prime finite fields. We adapt the idea to other characteristic sizes and to the different variants coupled with Factory.

After the smoothing step, the target is $\tilde{B}$-smooth with $\tilde{B} = L_Q(2/3, c_{\tilde{B}}) > B$, where $c_{\tilde{B}}$ is as in Lemma 1. Thanks to the previous steps, we know the virtual logarithms of the prime ideals in $\mathcal{O}_{\mathcal{K}_0}$ that are both factors of the target and of norm below $B$. It remains to compute the virtual logarithms of those of norm between $B$ and $\tilde{B}$. Let $q$ be such a prime ideal, of degree one and norm $q$. Define the special-q lattice $\mathcal{L}_q$ of dimension $2\eta$ over $\mathbb{Z}$, and of determinant $q$, that corresponds to the elements $(a(\iota), b(\iota))$ such that the ideal $(a(\iota) - b(\iota)\alpha_0)$ is divisible by $q$. Using the LLL algorithm, compute $(u_0, \dots, u_{2\eta-1})$ a basis of $\mathcal{L}_q$ where $\|u_i\|_{\infty} = \tilde{O}(p^{1/(2\eta)})$ for $i = 0, \dots, 2\eta - 1$. Let $\xi \in (0,1)$ a positive real number, to be determined later. The first step of the descent step consists in finding $(a(\iota), b(\iota)) \in \mathcal{L}_q$ such that:

$$ \frac{\mathcal{N}_0 (b(\iota) - a(\iota)\alpha_0)}{q} \text{ is } q^{\xi}\text{-smooth} \\ \text{and } \mathcal{N}_i (b(\iota) - a(\iota)\alpha_1) \text{ is } q^{\xi}\text{-smooth.} $$

This permits to express the virtual logarithm of $q$ as a linear combination of virtual logarithms of prime ideals of norm smaller than $q^{\xi}$. To recover the virtual logarithm of $q$, it is sufficient to repeat the process on each of the ideals in the linear combination until they are all in the factor basis.

We start by proving that the first step of the descent, i.e., finding $(a(\iota), b(\iota))$ as above, is the dominant step of the descent in terms of complexity. To descend the ideal $q$ to the factor basis, we construct a tree where the root is $q$ and the leaves are ideals in the factor basis. Each ideal that descends due to a pair $(a(\iota), b(\iota))$ introduces at most $\log_2(\mathcal{N}_0(b(\iota) - a(\iota)\alpha_0) + \log_2(\mathcal{N}_i(b(\iota) - a(\iota)\alpha_1))$ new nodes. By Corollary 6.4 in [Gui19], both norms are smaller than $Q$. Hence, the arity of the tree is less than $2\log_2 Q$, and its depth is smaller than the smallest integer $k$ such that $\xi^k \log \tilde{B} \le \log B$. Hence, $k = O((\log \log Q))$. The number of nodes in the tree is less than $(2\log_2(Q))^k = \exp(O(\log \log(Q)^2))$. Denote $\mathcal{C}$ the complexity of the first descent of $q$. We prove in the following paragraph that $\mathcal{C} = L_Q(1/3)$. Hence, the complexity of descending $q$ to the factor basis is dominated by $\exp(O(\log \log(Q)^2)) \cdot \mathcal{C} = \mathcal{C}$. This process is applied on all the prime factors of the target that are not in the factor basis, their number is in $O(\log Q)$. In short, the complexity of the descent step is the complexity of descending $q$, that is the complexity of finding $(a(\iota), b(\iota))$ as described above.

### B.2.1 Complexity of the descent step for NFS Factory and its variants.

For $\mu = (\mu_0, \dots, \mu_{2\eta-1})$ of infinity norm $S$, we look for “good” $(a(\iota), b(\iota))$ of the form $\mu_0 u_0 + \dots + \mu_{2\eta-1} u_{2\eta-1}$, either by sieving or ECM tests. Hence, $\|(a(\iota), b(\iota))\|_{\infty} = \tilde{O}(S q^{1/(2\eta)})$. We take $S^{2\eta} := L_Q(1/3, s)$ for a positive $s$ to be chosen. From the bound in §2.3, we get $\mathcal{N}_i(a(\iota) - b(\iota)\alpha_i) = \tilde{O}((S^{2\eta})^{\deg(f_i)/2} \|f_i\|_{\infty}^{\eta} q^{\deg(f_i)/2})$, for $i = 0, 1$. We assume the two following usual heuristics. The probability of each of the norms being $q^{\xi}$-smooth is the same as for a random integer of the same size, and the $q^{\xi}$-smoothness probability of both norms are independent. Under these assumptions, the probability that both norms are $q^{\xi}$-smooth is greater than the probability of a random integer of size the product of the
of the norms being $q^\xi$-smooth is the same as for a random integer of the same size, and the $q^\xi$-smoothness probability of both norms are independent. Under these assumptions, the probability that both norms are $q^\xi$-smooth is greater than the probability of a random integer of size the product of the norms being $q^\xi$-smooth. Besides, the product of the norms divided by $q$ is of size

$$N = \tilde{O} \left( (S^{2\eta})^{(\deg(f)+\deg(f_1))/2} \|f\|_{\infty}^{\eta} \|f_1\|_{\infty}^{\eta} q^{(\deg(f)+\deg(f_1))/2-1} \right).$$

Denote $q = L_Q(\alpha_q, c_q)$, where $1/3 \le \alpha_q \le 2/3$, with $c_q > c$ if $\alpha_q = 1/3$, and $c_q < c_{\tilde{B}}$ if $\alpha_q = 2/3$, since $B < q < \tilde{B}$. Hence, $q^\xi = L_Q(\alpha_q, \xi c_q)$. The complexity of a $q^\xi$-smoothness test by ECM is $L_Q(\alpha_q/2, (2\alpha_q\xi c_q)^{1/2})$. It is negligible compared to $L_Q(1/3)$ whenever $\alpha_q < 2/3$, and is equal to $L_Q(1/3, (4\xi c_q/3)^{1/2})$ if $\alpha_q = 2/3$.

*Large characteristic descent step for Factory.* Plugging the properties of the polynomials output by the GJL polynomial selection, with $\eta = 1$, we get $N = \tilde{O}((S^2)^{(2d+1)/2} Q^{1/(d+1)} q^{(2d+1)/2-1}$. Hence, $N = L_Q(2/3, s/\gamma + \gamma + c_q/\gamma)$ if $\alpha_q = 1/3$, and $N = L_Q(\alpha_q + 1/3, c_q/\gamma)$ if $\alpha_q > 1/3$. The asymptotic complexity of the descent step is the inverse of the probability of $N$ being $q^\xi$-smooth (see §2.3) times the cost of ECM. Thus this complexity is:

$$- L_Q \left( \frac{1}{3}, \frac{s}{3\gamma\xi c_q} + \frac{\gamma}{3\xi c_q} + \frac{1}{3\xi\gamma} \right), \text{ if } \alpha_q = \frac{1}{3}.$$

$$- L_Q \left( \frac{1}{3}, \frac{1}{3\xi\gamma} \right), \text{ if } \frac{1}{3} < \alpha_q < \frac{2}{3}.$$

$$- L_Q \left( \frac{1}{3}, \frac{1}{3\xi\gamma} + \sqrt{\frac{4\xi c_q}{3}} \right), \text{ if } \alpha_q = \frac{2}{3}.$$

When $q$ is small, i.e., $\alpha_q = 1/3$, the complexity of the descent grows as $q^\xi$ decreases, it is maximal when $\xi c_q = c$. Furthermore, the space of search of $(a, b)$ has to be equal to the inverse of the probability of $N$ being $q^\xi$-smooth, which translates into $s = s/(3\gamma\xi c) + \gamma/(3\xi c) + 1/(3\xi\gamma)$ after equalizing $\xi c_q$ and $c$. Thus, $s = (\gamma^2\xi + c)/((3c\gamma - 1)\xi)$. Taking for instance $\xi = 0.999$, we get the complexity of the descent in approximately $L_Q(1/3, 1.19)$, which is negligible compared to the smoothing step. The complexity of the descent when $\alpha_q$ is between 1/3 and 2/3 is upper bounded by the complexity when $q$ is of large size, i.e., $\alpha_q = 2/3$. In this last case, the complexity grows as $q$ grows, it is maximal when $c_q = c_{\tilde{B}}$. Hence, the complexity is upper bounded by $L_Q(1/3, 1/(3\xi\gamma) + (4c_{\tilde{B}}\xi/3)^{1/2})$. By minimizing the last quantity in $\xi$, we get $\xi = 1/(3c_{\tilde{B}}\gamma^2)^{1/3}$. In short, the complexity of descending $q$ is approximately $L_Q(1.3, 1.28)$, which is also negligible compared to the smoothing step. In conclusion, the complexity of the descent step in NFS Factory for large characteristic finite fields is negligible compared to the complexity of the smoothing step.

The analysis giving the best parameter choices for the other variants follows the same idea. We omit the optimization details. Table 10 recapitulates the asymptotic complexities for the individual logarithm step in all the variants.
norms being $q^\xi$-smooth. Besides, the product of the norms divided by $q$ is of size

$$N = \tilde{O}((S^{2\eta})^{(\deg(f)+\deg(f_1))/2} \|f\|_{\infty}^{\eta} \|f_1\|_{\infty}^{\eta} q^{(\deg(f)+\deg(f_1))/2-1}).$$

Denote $q = L_Q(\alpha_q, c_q)$, where $1/3 \le \alpha_q \le 2/3$, with $c_q > c$ if $\alpha_q = 1/3$, and $c_q < c_{\tilde{B}}$ if $\alpha_q = 2/3$, since $B < q < \tilde{B}$. Hence, $q^\xi = L_Q(\alpha_q, \xi c_q)$. The complexity of a $q^\xi$-smoothness test by ECM is $L_Q(\alpha_q/2, (2\alpha_q\xi c_q)^{1/2})$. It is negligible compared to $L_Q(1/3)$ whenever $\alpha_q < 2/3$, and is equal to $L_Q(1/3, (4\xi c_q/3)^{1/2})$ if $\alpha_q = 2/3$.

**Large characteristic descent step for Factory.** Plugging the properties of the GJL polynomials, with $\eta = 1$, we get

$$N = \tilde{O}((S^2)^{(2d+1)/2} Q^{1/(d+1)} q^{(2d+1)/2-1}).$$

Hence, $N = L_Q(2/3, s/\gamma + \gamma + c_q/\gamma)$ if $\alpha_q = 1/3$, and $N = L_Q(\alpha_q + 1/3, c_q/\gamma)$ if $\alpha_q > 1/3$. The asymptotic complexity of the descent step is the inverse of the probability of $N$ being $q^\xi$-smooth (see §2.3) times the cost of ECM. Thus this complexity is:

$$L_Q \left( \frac{1}{3}, \frac{s}{3\gamma\xi c_q} + \frac{\gamma}{3\xi c_q} + \frac{1}{3\xi\gamma} \right) \quad \text{if } \alpha_q = \frac{1}{3}, \\ L_Q \left( \frac{1}{3}, \frac{1}{3\xi\gamma} \right) \quad \text{if } \frac{1}{3} < \alpha_q < \frac{2}{3}, \\ L_Q \left( \frac{1}{3}, \frac{1}{3\xi\gamma} + \sqrt{\frac{4\xi c_q}{3}} \right) \quad \text{if } \alpha_q = \frac{2}{3}.$$

When $q$ is small, i.e., $\alpha_q = 1/3$, the complexity of the descent grows as $q^\xi$ decreases, it is maximal when $\xi c_q = c$. Furthermore, the space of search of $(a, b)$ has to be equal to the inverse of the probability of $N$ being $q^\xi$-smooth, which translates into $s = s/(3\gamma\xi c) + \gamma/(3\xi c) + 1/(3\xi\gamma)$ after equalizing $\xi c_q$ and $c$. Thus, $s = (\gamma^2\xi + c)/(3c\gamma - 1)\xi$. Taking for instance $\xi = 0.999$, we get the complexity of the descent in approximately $L_Q(1/3, 1.19)$, which is negligible compared to the smoothing step. The complexity of the descent when $\alpha_q$ is between $1/3$ and $2/3$ is upper bounded by the complexity when $q$ is of large size, i.e., $\alpha_q = 2/3$. In this last case, the complexity grows as $q$ grows, it is maximal when $c_q = c_{\tilde{B}}$. Hence, the complexity is upper bounded by $L_Q(1/3, 1/(3\xi\gamma) + (4c_{\tilde{B}}\xi/3)^{1/2})$. By minimizing the last quantity in $\xi$, we get $\xi = 1/(3c_{\tilde{B}}\gamma^2)^{1/3}$. In short, the complexity of descending $q$ is approximately $L_Q(1.3, 1.28)$, which is also negligible compared to the smoothing step. In conclusion, the complexity of the descent step in NFS Factory for large characteristic finite fields is negligible compared to the complexity of the smoothing step.

The analysis giving the best parameter choices for the other variants follows the same idea. We omit the optimization details. Table 11 recapitulates the asymptotic complexities for the individual logarithm step in all the variants.

**Boundary case descent step for Factory.** We target finite fields $\mathbb{F}_{p_i^n}$ where $p_i \approx Q^{1/n} = L_Q(2/3, c_p)$, with $c_p$ a positive constant. When the polynomial selection method used is GJL, the complexity analysis of the descent step is the same as for NFS Factory in large characteristic. It is negligible compared to the smoothing step.

When using Conjugation, instead of looking for a “good” $(a, b)$ in $\mathcal{L}_q$, we look for a “good” vector of dimension $\tilde{t}$, where $\tilde{t}$ is a positive integer greater than or equal to two. Hence, $\eta = 1$, the dimension of $\mathcal{L}_q$ is $\tilde{t}$ and its determinant is $q$. We need to adapt the formula given for $N$ at the beginning of this Appendix and use instead the formula at the
<table><caption>**Table 10.** Asymptotic complexities of the individual logarithm step and the per-field step in NFS Factory and its variants. This table recap an approximation of $c$ when the complexities are expressed as $L_Q(1/3, c)$. For NFS at the boundary case, the complexity depends on the finite field size. We refer to a figure plotting these complexities. For SNFS in medium characteristic (with or without Tower), the complexities depend on an integer $\lambda$. We refer to tables giving the complexities for various values of $\lambda$.</caption><thead><tr><th>Algorithm</th><th>Characteristic</th><th>Smoothing</th><th>Descent</th><th>computation per field</th></tr></thead><tbody><tr><td rowspan="3">NFS Factory</td><td>Large</td><td>1.30</td><td>1.28</td><td><b>1.64</b></td></tr><tr><td>Boundary case</td><td></td><td></td><td>Figure 11</td></tr><tr><td>Medium</td><td>1.30</td><td>1.43</td><td><b>1.73</b></td></tr><tr><td>TNFS Factory</td><td>Medium</td><td>1.30</td><td>1.28</td><td><b>1.37</b></td></tr><tr><td rowspan="2">SNFS</td><td>Large</td><td>1.30</td><td>1.06</td><td><b>1.39</b></td></tr><tr><td>Medium</td><td></td><td></td><td>Table 12</td></tr><tr><td>STNFS Factory</td><td>Medium</td><td></td><td></td><td>Table 13</td></tr></tbody></table>

*Boundary case descent step for Factory.* We target finite fields $\mathbb{F}_{p_i^n}$ where $p_i \approx Q^{1/n} = L_Q(2/3, c_p)$, with $c_p$ a positive constant. When the polynomial selection method used is GJL, the complexity analysis of the descent step is the same as for NFS Factory in large characteristic. It is negligible compared to the smoothing step.

When using Conjugation, instead of looking for a “good” $(a, b)$ in $\mathcal{L}_q$, we look for a “good” vector of dimension $\tilde{t}$, where $\tilde{t}$ is a positive integer greater than or equal to two. Hence, $\eta = 1$, the dimension of $\mathcal{L}_q$ is $\tilde{t}$ and its determinant is $q$. We need to adapt the formula given for $N$ at the beginning of this Appendix and use instead the formula at the beginning of §2.3 with the properties of the polynomials output by Conjugation. In short, taking $S^{\tilde{t}} = L_Q(1/3, s)$, we get $N = \tilde{O}((S^{\tilde{t}})^{3n/\tilde{t}}Q^{(\tilde{t}-1)/(2n)}q^{3n/\tilde{t}-1})$. Hence $N = L_Q(2/3, 3s/(\tilde{t}c_p) + (\tilde{t}-1)c_p/2 + 3c_q/(\tilde{t}c_p))$ if $\alpha_q = 1/3$, and $N = L_Q(\alpha_q + 1/3, 3c_q/(\tilde{t}c_p))$ if $\alpha_q > 1/3$. The complexity of the descent step is then:

$$ - L_Q \left( \frac{1}{3}, \frac{s}{\xi c_q c_p \tilde{t}} + \frac{(\tilde{t}-1)c_p}{6\xi c_q} + \frac{1}{\xi \tilde{t} c_p} \right), \text{ if } \alpha_q = \frac{1}{3}. $$

$$ - L_Q \left( \frac{1}{3}, \frac{1}{\xi \tilde{t} c_p} \right), \text{ if } \frac{1}{3} < \alpha_q < \frac{2}{3}. $$

$$ - L_Q \left( \frac{1}{3}, \frac{1}{\xi \tilde{t} c_p} + \sqrt{\frac{4\xi c_q}{3}} \right), \text{ if } \alpha_q = \frac{2}{3}. $$

Figure 11 plots the asymptotic complexities of different parts of Factory: the smoothing step, the descent step for both small and large $q$, and the computation in each step. We see that both the descent step and the smoothing step are negligible with regard to the computation per field.

*Medium characteristic descent step for Factory.* Here the analysis is quite close from the one at the boundary case for Conjugation. Again, we look for a “good” vector of dimension $\tilde{t}$, where $\tilde{t}$ is taken equal to $\tilde{\delta}n(\log(Q)/\log\log(Q))^{-1/3+o(1)}$. Hence, $\eta = 1$, the dimension of $\mathcal{L}_q$ is $\tilde{t}$ and its determinant is $q$. Taking $S^{\tilde{t}} =$
<table><caption>**Table 11:** Asymptotic complexities of the individual logarithm step and the *per-field* step in NFS Factory and its variants. This table recaps approximations of *c* when the complexities are expressed as $L_Q(1/3, c)$.</caption><thead><tr><th>Algorithm</th><th>Characteristic</th><th>Smoothing</th><th>Descent</th><th>computation per field</th></tr></thead><tbody><tr><td rowspan="3">NFS Factory</td><td>Large</td><td>1.30</td><td>1.28</td><td><strong>1.64</strong></td></tr><tr><td>Boundary case</td><td></td><td colspan="2">Figure 12</td></tr><tr><td>Medium</td><td>1.30</td><td>1.43</td><td><strong>1.73</strong></td></tr><tr><td>TNFS Factory</td><td>Medium</td><td>1.30</td><td>1.28</td><td><strong>1.37</strong></td></tr><tr><td rowspan="2">SNFS</td><td>Large</td><td>1.30</td><td>1.06</td><td><strong>1.39</strong></td></tr><tr><td>Medium</td><td></td><td colspan="2">Table 13</td></tr><tr><td>STNFS Factory</td><td>Medium</td><td></td><td colspan="2">Table 14</td></tr></tbody></table>

beginning of §2.3 with the properties of the polynomials output by Conjugation. In short, taking $S^t = L_Q(1/3, s)$, we get

$$N = \tilde{O}((S^t)^{3n/\tilde{t}} Q^{(\tilde{t}-1)/(2n)} q^{3n/\tilde{t}-1}).$$

Hence $N = L_Q(2/3, 3s/(\tilde{t}c_p) + (\tilde{t}-1)c_p/2 + 3c_q/(\tilde{t}c_p))$ if $\alpha_q = 1/3$, and $N = L_Q(\alpha_q + 1/3, 3c_q/(\tilde{t}c_p))$ if $\alpha_q > 1/3$. The complexity of the descent step is then:

$$ 
\begin{aligned}
L_Q \left( \frac{1}{3}, \frac{s}{\xi c_q c_p \tilde{t}} + \frac{(\tilde{t}-1)c_p}{6\xi c_q} + \frac{1}{\xi \tilde{t} c_p} \right) & \quad \text{if } \alpha_q = \frac{1}{3}, \\
L_Q \left( \frac{1}{3}, \frac{1}{\xi \tilde{t} c_p} \right) & \quad \text{if } \frac{1}{3} < \alpha_q < \frac{2}{3}, \\
L_Q \left( \frac{1}{3}, \frac{1}{\xi \tilde{t} c_p} + \sqrt{\frac{4\xi c_q}{3}} \right) & \quad \text{if } \alpha_q = \frac{2}{3}.
\end{aligned}
$$

Figure 12 plots the asymptotic complexities of different parts of Factory: the smoothing step, the descent step for both small and large $q$, and the computation in each step. We see that both the descent step and the smoothing step are negligible with regard to the computation per field.

**Medium characteristic descent step for Factory.** Here the analysis is quite close from the one at the boundary case for Conjugation. Again, we look for a “good” vector of dimension $\tilde{t}$, where $\tilde{t}$ is taken equal to $\tilde{\delta}n(\log(Q)/\log\log(Q))^{-1/3+o(1)}$. Hence, $\eta = 1$, the dimension of $\mathcal{L}_q$ is $\tilde{t}$ and its determinant is $q$. Taking $S^t = L_Q(1/3, s)$, we get

$$N = \tilde{O}((S^t)^{3n/\tilde{t}} Q^{(\tilde{t}-1)/(2n)} q^{3n/\tilde{t}-1}).$$

Hence we can write the norm $N = L_Q(2/3, 3s/\tilde{\delta} + \tilde{\delta}/2 + 3c_q/\tilde{\delta})$ if $\alpha_q = 1/3$, and $N = L_Q(\alpha_q + 1/3, 3c_q/\tilde{\delta})$ if $\alpha_q > 1/3$. The asymptotic complexity of the descent step depends on the size of $q$, it is:

$$ 
\begin{aligned}
L_Q \left( \frac{1}{3}, \frac{s}{\xi c_q \tilde{\delta}} + \frac{\tilde{\delta}}{6\xi c_q} + \frac{1}{\xi \tilde{\delta}} \right) & \quad \text{if } \alpha_q = \frac{1}{3}, \\
L_Q \left( \frac{1}{3}, \frac{1}{\xi \tilde{\delta}} \right) & \quad \text{if } \frac{1}{3} < \alpha_q < \frac{2}{3}, \\
L_Q \left( \frac{1}{3}, \frac{1}{\xi \tilde{\delta}} + \sqrt{\frac{4\xi c_q}{3}} \right) & \quad \text{if } \alpha_q = \frac{2}{3}.
\end{aligned}
$$
<figure><img src="image_5.png" /><figcaption>Fig. 11. Asymptotic complexities of some steps inside NFS Factory at the boundary case. Target finite fields have characteristic $p$ such that $p = L_{p^n}(2/3, c_p)$. This graph shows how $c$ varies as a function of $c_p$ when the complexities are expressed as $L_{p^n}(1/3, c)$.</figcaption></figure>

$L_Q(1/3, s)$, we get $N = \tilde{O}((S^i)^{3n/\tilde{t}}Q^{(\tilde{t}-1)/(2n)}q^{3n/\tilde{t}-1})$. Hence we can write the norm $N = L_Q(2/3, 3s/\tilde{\delta}+\tilde{\delta}/2+3c_q/\tilde{\delta})$ if $\alpha_q = 1/3$, and $N = L_Q(\alpha_q+1/3, 3c_q/\tilde{\delta})$ if $\alpha_q > 1/3$. The asymptotic complexity of the descent step depends on the size of $q$, it is:

$$- L_Q \left( \frac{1}{3}, \frac{s}{\xi c_q \tilde{\delta}} + \frac{\tilde{\delta}}{6 \xi c_q} + \frac{1}{\xi \tilde{\delta}} \right), \text{ if } \alpha_q = \frac{1}{3}.$$

$$- L_Q \left( \frac{1}{3}, \frac{1}{\xi \tilde{\delta}} \right), \text{ if } \frac{1}{3} < \alpha_q < \frac{2}{3}.$$

$$- L_Q \left( \frac{1}{3}, \frac{1}{\xi \tilde{\delta}} + \sqrt{\frac{4 \xi c_q}{3}} \right), \text{ if } \alpha_q = \frac{2}{3}.$$

The hardest $q$ to descend is the one of small size with a complexity in approximately $L_Q(1/3, 1.43)$. The descent step has a complexity that is dominant compared to the smoothness step, but negligible compared to the *per-field* step.

*Medium characteristic descent step for TNFS Factory.* We consider Conjugation for the polynomial selection. We get $N = \tilde{O}((S^{2\eta})^{3\kappa/2}Q^{1/(2\kappa)}q^{3\kappa/2-1})$. Hence, $N = L_Q(2/3, 3s/(2c_\kappa)+c_\kappa/2+3c_q/(2c_\kappa))$ if $\alpha_q = 1/3$ and $N = L_Q(2/3, 3c_q/(2c_\kappa))$ if $\alpha_q > 1/3$. The complexity of the descent step is:
<figure><img src="image_6.png" /><figcaption>Fig. 12: Asymptotic complexities of some steps inside NFS Factory at the boundary case. Target finite fields have characteristic $p$ such that $p = L_{p^n}(2/3, c_p)$. This graph shows how $c$ varies as a function of $c_p$ when the complexities are expressed as $L_{p^n}(1/3, c)$.</figcaption></figure>

The hardest $q$ to descend is the one of small size with a complexity in approximately $L_Q(1/3, 1.43)$. The descent step has a complexity that is dominant compared to the smoothness step, but negligible compared to the *per-field* step.

**Medium characteristic descent step for TNFS Factory.** We consider Conjugation for the polynomial selection. We get

$$N = \tilde{O}((S^{2\eta})^{3\kappa/2} Q^{1/(2\kappa)} q^{3\kappa/2-1}).$$

Hence, $N = L_Q(2/3, 3s/(2c_\kappa) + c_\kappa/2 + 3c_q/(2c_\kappa))$ if $\alpha_q = 1/3$ and $N = L_Q(2/3, 3c_q/(2c_\kappa))$ if $\alpha_q > 1/3$. The complexity of the descent step is:

$$L_Q \left( \frac{1}{3}, \frac{s}{2\xi c_q c_\kappa} + \frac{c_\kappa}{6\xi c_q} + \frac{1}{2\xi c_\kappa} \right) \quad \text{if } \alpha_q = \frac{1}{3},$$

$$L_Q \left( \frac{1}{3}, \frac{1}{2\xi c_\kappa} \right) \quad \text{if } \frac{1}{3} < \alpha_q < \frac{2}{3},$$

$$L_Q \left( \frac{1}{3}, \frac{1}{2\xi c_\kappa} + \sqrt{\frac{4\xi c_q}{3}} \right) \quad \text{if } \alpha_q = \frac{2}{3}.$$

The hardest $q$ to descend is the one of large size with a complexity in approximately $L_Q(1/3, 1.28)$, which is negligible compared to the complexity of the smoothness step.

**Large characteristic descent step for SNFS Factory.** Plugging the properties of the polynomials given by the Joux-Pierrot polynomial selection, we get the norm

$$N = \tilde{O}((S^2)^{n(\lambda+1)/2} Q^{1/(\lambda n)} q^{n(\lambda+1)/2-1}).$$
$$-L_Q\left(\frac{1}{3}, \frac{s}{2\xi c_q c_\kappa} + \frac{c_\kappa}{6\xi c_q} + \frac{1}{2\xi c_\kappa}\right), \text{ if } \alpha_q = \frac{1}{3}.$$

$$-L_Q\left(\frac{1}{3}, \frac{1}{2\xi c_\kappa}\right), \text{ if } \frac{1}{3} < \alpha_q < \frac{2}{3}.$$

$$-L_Q\left(\frac{1}{3}, \frac{1}{2\xi c_\kappa} + \sqrt{\frac{4\xi c_q}{3}}\right), \text{ if } \alpha_q = \frac{2}{3}.$$

The hardest q to descend is the one of large size with a complexity in approximately $L_Q(1/3, 1.28)$, which is negligible compared to the complexity of the smoothness step.

*Large characteristic descent step for SNFS Factory.* Plugging the properties of the polynomials given by the Joux-Pierrot polynomial selection, we get the norm $N = \tilde{O}((S^2)^{n(\lambda+1)/2}Q^{1/(\lambda n)}q^{n(\lambda+1)/2-1})$. Hence, $N = L_Q(2/3, s/(2c_\lambda) + c_\lambda + c_q/(2\lambda))$ if $\alpha_q = 1/3$, and $N = L_Q(\alpha_q + 1/3, c_q/(2\lambda))$ if $\alpha_q > 1/3$. The complexity of the descent step is:

$$-L_Q\left(\frac{1}{3}, \frac{s}{6\xi c_q c_\lambda} + \frac{c_\lambda}{3\xi c_q} + \frac{1}{6\xi c_\lambda}\right), \text{ if } \alpha_q = \frac{1}{3}.$$

$$-L_Q\left(\frac{1}{3}, \frac{1}{6\xi c_\lambda}\right), \text{ if } \frac{1}{3} < \alpha_q < \frac{2}{3}.$$

$$-L_Q\left(\frac{1}{3}, \frac{1}{6\xi c_\lambda} + \sqrt{\frac{4\xi c_q}{3}}\right), \text{ if } \alpha_q = \frac{2}{3}.$$

The hardest q to descend is the one of large size with a complexity in approximately $L_Q(1/3, 1.06)$, which is negligible compared to the complexity of the smoothness step.

*Medium characteristic descent step for SNFS Factory.* We look for a “good” vector of dimension $\tilde{t}$, where $\tilde{t}$ is taken equal to $\tilde{\delta}n(\log(Q)/\log\log(Q))^{-1/3+o(1)}$. Therefore, $\eta = 1$, the dimension of $\mathcal{L}_q$ is $\tilde{t}$ and its determinant is $q$. We use the formula for $N$ of §2.3, with the properties of the polynomials output by the Joux-Pierrot method. Writing $S^{\tilde{t}} = L_Q(1/3, s)$, we obtain

$$N = \tilde{O}((S^{\tilde{t}})^{n(\lambda+1)/\tilde{t}}Q^{(\tilde{t}-1)/(\lambda n)}q^{n(\lambda+1)/\tilde{t}-1}).$$

Hence, $N = L_Q(2/3, s(\lambda+1)/\tilde{\delta} + \tilde{\delta}/\lambda + (\lambda+1)c_q/\tilde{\delta})$ if $\alpha_q = 1/3$, and $N = L_Q(\alpha_q + 1/3, (\lambda+1)c_q/\tilde{\delta})$ if $\alpha_q > 1/3$. The complexity of the descent step is:

$$-L_Q\left(\frac{1}{3}, \frac{s(\lambda+1)}{3\xi c_q \tilde{\delta}} + \frac{\tilde{\delta}}{3\xi c_q \lambda} + \frac{\lambda+1}{3\xi \tilde{\delta}}\right), \text{ if } \alpha_q = \frac{1}{3}.$$

$$-L_Q\left(\frac{1}{3}, \frac{\lambda+1}{3\xi \tilde{\delta}}\right), \text{ if } \frac{1}{3} < \alpha_q < \frac{2}{3}.$$

$$-L_Q\left(\frac{1}{3}, \frac{\lambda+1}{3\xi \tilde{\delta}} + \sqrt{\frac{4\xi c_q}{3}}\right), \text{ if } \alpha_q = \frac{2}{3}.$$

As previously, the hardest q to descend is the one of large size. Table 12 presents approximate values of the complexity for various values of $\lambda$. The complexity of the descent step is always dominant compared to the smoothing step, but still negligible compared to the *per-field* step.
<table><caption>**Table 13:** Asymptotic complexities for different part of medium characteristic SNFS Factory. These complexities are expressed as $L_Q(1/3, c)$ and only an approximation of $c$ is given. The individual logarithm phase, that consists of the smoothing step and the descent step, is always negligible with regard to the other steps in the computation per field.</caption><thead><tr><th>λ</th><th>Smoothing</th><th>Descent</th><th>computation per field</th></tr></thead><tbody><tr><td>λ = 2</td><td>1.43</td><td>1.30</td><td><b>1.73</b></td></tr><tr><td>λ = 3</td><td>1.46</td><td>1.30</td><td><b>1.58</b></td></tr><tr><td>λ = 4</td><td>1.33</td><td>1.30</td><td><b>1.64</b></td></tr><tr><td>λ = 5</td><td>1.36</td><td>1.30</td><td><b>1.57</b></td></tr></tbody></table>

Hence, $N = L_Q(2/3, s/(2c_λ) + c_λ + c_q/(2λ))$ if $α_q = 1/3$, and $N = L_Q(α_q + 1/3, c_q/(2λ))$ if $α_q > 1/3$. The complexity of the descent step is:

$$ 
\begin{array}{ll}
L_Q \left( \frac{1}{3}, \frac{s}{6\xi c_q c_\lambda} + \frac{c_\lambda}{3\xi c_q} + \frac{1}{6\xi c_\lambda} \right) & \text{if } \alpha_q = \frac{1}{3}, \\
L_Q \left( \frac{1}{3}, \frac{1}{6\xi c_\lambda} \right) & \text{if } \frac{1}{3} < \alpha_q < \frac{2}{3}, \\
L_Q \left( \frac{1}{3}, \frac{1}{6\xi c_\lambda} + \sqrt{\frac{4\xi c_q}{3}} \right) & \text{if } \alpha_q = \frac{2}{3}.
\end{array}
$$

The hardest $q$ to descend is the one of large size with a complexity in approximately $L_Q(1/3, 1.06)$, which is negligible compared to the complexity of the smoothness step.

**Medium characteristic descent step for SNFS Factory.** We look for a “good” vector of dimension $\tilde{t}$, where $\tilde{t}$ is taken equal to $\tilde{\delta}n(\log(Q)/\log\log(Q))^{-1/3+o(1)}$. Therefore, $\eta = 1$, the dimension of $\mathcal{L}_q$ is $\tilde{t}$ and its determinant is $q$. We use the formula for $N$ of §2.3, with the properties of the polynomials output by the Joux-Pierrot method. Writing $S^{\tilde{t}} = L_Q(1/3, s)$, we obtain

$$ N = \tilde{O}((S^{\tilde{t}})^{n(\lambda+1)/\tilde{t}} Q^{(\tilde{t}-1)/(\lambda n)} q^{n(\lambda+1)/\tilde{t}-1}). $$

Hence, $N = L_Q(2/3, s(\lambda + 1)/\tilde{\delta} + \tilde{\delta}/\lambda + (\lambda + 1)c_q/\tilde{\delta})$ if $α_q = 1/3$, and $N = L_Q(α_q + 1/3, (\lambda + 1)c_q/\tilde{\delta})$ if $α_q > 1/3$. The complexity of the descent step is:

$$ 
\begin{array}{ll}
L_Q \left( \frac{1}{3}, \frac{s(\lambda+1)}{3\xi c_q \tilde{\delta}} + \frac{\tilde{\delta}}{3\xi c_q \lambda} + \frac{\lambda+1}{3\xi \tilde{\delta}} \right) & \text{if } \alpha_q = \frac{1}{3}, \\
L_Q \left( \frac{1}{3}, \frac{\lambda+1}{3\xi \tilde{\delta}} \right) & \text{if } \frac{1}{3} < \alpha_q < \frac{2}{3}, \\
L_Q \left( \frac{1}{3}, \frac{\lambda+1}{3\xi \tilde{\delta}} + \sqrt{\frac{4\xi c_q}{3}} \right) & \text{if } \alpha_q = \frac{2}{3}.
\end{array}
$$

As previously, the hardest $q$ to descend is the one of large size. Table 13 presents approximate values of the complexity for various values of $λ$. The complexity of the descent step is always dominant compared to the smoothing step, but still negligible compared to the *per-field* step.

**Medium characteristic descent step for STNFS Factory.** With Joux-Pierrot selection and the usual notations, we get

$$ N = \tilde{O}((S^{2\eta})^{\kappa(\lambda+1)/2} Q^{1/(\lambda\kappa)} q^{\kappa(\lambda+1)/2-1}). $$
<table><caption>**Table 12.** Asymptotic complexities for different part of medium characteristic SNFS Factory. These complexities are expressed as $L_Q(1/3, c)$ and only an approximation of $c$ is given. The individual logarithm phase, that consists of the smoothing step and the descent step, is always negligible with regard to the other steps in the computation per field.</caption><thead><tr><th>λ</th><th>Smoothing</th><th>Descent</th><th>computation per field</th></tr></thead><tbody><tr><td>λ = 2</td><td>1.43</td><td>1.30</td><td><b>1.73</b></td></tr><tr><td>λ = 3</td><td>1.46</td><td>1.30</td><td><b>1.58</b></td></tr><tr><td>λ = 4</td><td>1.33</td><td>1.30</td><td><b>1.64</b></td></tr><tr><td>λ = 5</td><td>1.36</td><td>1.30</td><td><b>1.57</b></td></tr></tbody></table>

*Medium characteristic descent step for STNFS Factory.* With Joux-Pierrot selection and the usual notations, we get, $N = \tilde{O}((S^{2\eta})^{\kappa(\lambda+1)/2}Q^{1/(\lambda\kappa)}q^{\kappa(\lambda+1)/2-1})$. Hence, $N = L_Q(2/3, (\lambda+1)s/(2c_\kappa) + c_\kappa/\lambda + (\lambda+1)c_q/(2c_\kappa))$ if $\alpha_q = 1/3$, and $N = L_Q(\alpha_q + 1/3, (\lambda+1)c_q/(2c_\kappa))$ if $\alpha_q > 1/3$. The complexity of the descent step depends on $\lambda$, it is:

$$-L_Q\left(\frac{1}{3}, \frac{s(\lambda+1)}{6\xi c_q c_\kappa} + \frac{c_\kappa}{3\xi c_q \lambda} + \frac{\lambda+1}{6\xi c_\kappa}\right), \text{ if } \alpha_q = \frac{1}{3}.$$

$$-L_Q\left(\frac{1}{3}, \frac{\lambda+1}{6\xi c_\kappa}\right), \text{ if } \frac{1}{3} < \alpha_q < \frac{2}{3}.$$

$$-L_Q\left(\frac{1}{3}, \frac{\lambda+1}{6\xi c_\kappa} + \sqrt{\frac{4\xi c_q}{3}}\right), \text{ if } \alpha_q = \frac{2}{3}.$$

The hardest $q$ to descend is the one of large size. Table 13 presents approximate values of the complexity for different small values of $\lambda$. We see that the asymptotic complexity of both the descent step is negligible compared to the complexity of the smoothing step. Note that both the smoothing and the descent are negligible with regard to the computation in each field when $\lambda$ is lower of equal to 4, but when $\lambda = 5$ the smoothing step starts to be dominant.

<table><caption>**Table 13.** Asymptotic complexities for different part of medium characteristic STNFS Factory. These complexities are expressed as $L_Q(1/3, c)$ and only an approximation of $c$ is given. The dominant step is indicated in bold.</caption><thead><tr><th>λ</th><th>Descent</th><th>Smoothing</th><th>computation per field</th></tr></thead><tbody><tr><td>λ = 2</td><td>1.26</td><td>1.30</td><td><b>1.37</b></td></tr><tr><td>λ = 3</td><td>1.04</td><td>1.30</td><td><b>1.38</b></td></tr><tr><td>λ = 4</td><td>1.06</td><td>1.30</td><td><b>1.30</b></td></tr><tr><td>λ = 5</td><td>1.08</td><td>1.30</td><td><b>1.31</b></td></tr></tbody></table>
<table><caption>**Table 14:** Asymptotic complexities for different part of medium characteristic STNFS Factory. These complexities are expressed as $L_Q(1/3, c)$ and only an approximation of c is given. The dominant step is indicated in bold.</caption><thead><tr><th>λ</th><th>Descent</th><th>Smoothing</th><th>computation per field</th></tr></thead><tbody><tr><td>λ = 2</td><td>1.26</td><td>1.30</td><td><b>1.37</b></td></tr><tr><td>λ = 3</td><td>1.04</td><td>1.30</td><td><b>1.38</b></td></tr><tr><td>λ = 4</td><td>1.06</td><td>1.30</td><td><b>1.30</b></td></tr><tr><td>λ = 5</td><td>1.08</td><td>1.30</td><td><b>1.31</b></td></tr></tbody></table>

Hence, $N = L_Q(2/3, (\lambda + 1)s/(2c_\kappa) + c_\kappa/\lambda + (\lambda + 1)c_q/(2c_\kappa))$ if $\alpha_q = 1/3$, and $N = L_Q(\alpha_q + 1/3, (\lambda + 1)c_q/(2c_\kappa))$ if $\alpha_q > 1/3$. The complexity of the descent step depends on $\lambda$, it is:

$$L_Q\left(\frac{1}{3}, \frac{s(\lambda+1)}{6\xi c_q c_\kappa} + \frac{c_\kappa}{3\xi c_q \lambda} + \frac{\lambda+1}{6\xi c_\kappa}\right) \quad \text{if } \alpha_q = \frac{1}{3},$$

$$L_Q\left(\frac{1}{3}, \frac{\lambda+1}{6\xi c_\kappa}\right) \quad \text{if } \frac{1}{3} < \alpha_q < \frac{2}{3},$$

$$L_Q\left(\frac{1}{3}, \frac{\lambda+1}{6\xi c_\kappa} + \sqrt{\frac{4\xi c_q}{3}}\right) \quad \text{if } \alpha_q = \frac{2}{3}.$$

The hardest $q$ to descend is the one of large size. Table 14 presents approximate values of the complexity for different small values of $\lambda$. We see that the asymptotic complexity of both the descent step is negligible compared to the complexity of the smoothing step. Note that both the smoothing and the descent are negligible with regard to the computation in each field when $\lambda$ is lower of equal to 4, but when $\lambda = 5$ the smoothing step starts to be dominant.