Andrea Lesavourey
email: andrea.lesavourey@irisa.fr

Thomas Plantard
email: thomas.plantard@gmail.com

Willy Susilo
email: wsusilo@uow.edu.au.

Computing roots of polynomials over number fields using complex embeddings

Keywords: 2020 Mathematics Subject Classification. 11R09, 11Y40 polynomial roots, number fields, relative extensions, LLL, complex embeddings

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

In the past few years, the rise of cryptographic protocols using the structure of number fields has driven attention to computational number theory. Indeed, in order to obtain efficient implementations of such cryptosystems as well as testing their security, fast computations over number fields are required. In particular, number field units and S-units are the main objects used to retrieve short generators of principal ideals [START_REF] Cramer | Recovering Short Generators of Principal Ideals in Cyclotomic Rings[END_REF][START_REF] Bauch | Short Generators Without Quantum Computers: The Case of Multiquadratics[END_REF][START_REF] Lesavourey | Short Principal Ideal Problem in multicubic fields[END_REF] and short elements of general ideal lattices [START_REF] Cramer | Short Stickelberger Class Relations and Application to Ideal-SVP[END_REF][START_REF] Pellet-Mary | Approx-SVP in Ideal Lattices with Pre-processing[END_REF][START_REF] Bernard | Twisted-PHS: Using the Product Formula to Solve Approx-SVP in Ideal Lattices[END_REF][START_REF] Bernard | Log-S-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP[END_REF] respectively. Their computation commonly requires a saturation process [START_REF] Pohst | Algorithmic Algebraic Number Theory[END_REF][START_REF] Fieker | On Reconstruction of Algebraic Numbers[END_REF][START_REF] Biasse | Norm relations and computational problems in number fields[END_REF], which includes a necessary step of n-th roots computations. This task is a special case of solving a polynomial equation with coefficients in a number field.

We are therefore interested in the following problem. Given K a number field and f (T ) ∈ K[T ], find the roots of f (T ) in K i.e. find Z K (f ) = {x ∈ K | f (x) = 0}. As a matter of fact we will only consider the cases such that all the roots can be expressed as integral combinations of a known basis of K i.e. such that:

∃(b i ) i ∈ K n , ∀x ∈ Z K (f ), ∃(x i ) i ∈ Z n | x = x 1 b 1 + • • • + x n b n .
We believe that we are not too restrictive as this is often the case in standard computations, such as S-units computations or the Number Field Sieve [START_REF] Lenstra | The number field sieve[END_REF][START_REF] Thomé | Square Root Algorithms for the Number Field Sieve[END_REF].

The state of the art algorithm to solve this problem -that we will call the algebraic or p-adic method -is implemented in softwares such as Magma or Pari/GP [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF][START_REF]PARI/GP version 2.11.2[END_REF]. It follows the ideas used to factorise polynomials over number fields developed for example in [START_REF] Belabas | A relative van Hoeij algorithm over number fields[END_REF][START_REF] Fieker | On Reconstruction of Algebraic Numbers[END_REF][START_REF] Pohst | Factoring polynomials over global fields I[END_REF][START_REF] Roblot | Polynomial factorization algorithms over number fields[END_REF] and uses finite places. More precisely, the procedure is as follows:

(1) pick a prime ideal p which defines an isomorphism between O K /p and F p s for some prime number p ∈ Z;

(2) compute the roots modulo p in F p s [X];

(3) lift these to elements to K modulo a power p k ; (4) if p k is large enough compared to the size of the solutions and it is given by a LLL-reduced basis then we can recover a solution x given y ≡ x mod p k .

In practice, the method requires three main computational operations:

(1) compute first an "approximation" of the solutions;

(2) compute a reduced basis of a lattice;

(3) retrieve the solutions from the approximation using the lattice.

The third step -called the decoding phase -can be seen as solving instances of the Bounded Distance Decoding (BDD) problem. However, it is possible to use complex embeddings instead of prime ideals. Indeed, it is known at least since the seminal paper introducing the LLL algorithm [START_REF] Lenstra | Factoring Polynomials with Rational Coefficients[END_REF] how to use lattices in order to find short integral relations between algebraic numbers or find the irreducible polynomial of a number field element. As an example, assume one knows approximations of real numbers α 1 , . . . , α n . Now define the embedding Here C is a large coefficient used to ensure the shortness of the solution. Reducing this basis would allow us to retrieve a short vector (λ i ) i∈ 1,n such that C n i=1 λ i α i is small. Note that this strategy can be seen as solving an instance of the Shorstest Vector Problem (SVP). Similarly it is common to use LLL algorithm to solve knapsack problems. Assume we are given (α 1 , . . . , α n ) ∈ Z n and S ∈ Z, and that we want to find a short vector (λ 1 , . . . , λ n ) such that Again a LLL reduction would yield a small solution of the linear equation.

Z n -→ R n+1 (λ i ) i∈ 1,n -→ (C n i=1 λ i α i ,

Our work.

One can combine both approaches to retrieve the coefficient of x ∈ Z[B] from an embedding σ i (x), where B = (b 1 , . . . , b n ) is a Q-basis of K. This is done through solving an instance of BDD. For all j ∈ 1, n , denote by β j an approximation of σ i (b j ) and S an approximation if σ i (x). Now consider (x i ) i∈ 1,n ∈ Z n the coefficients of x in the basis B. Then one can expect S -n i=1 x i β i to be close to 0. Thus solving a BDD instance with input the row matrix

       -β 1 1 0 . . . 0 -β 2 0 1 . . . . . . . . . . . . . . . . . . 0 -β n 0 . . . 0 1       
and target vector [S, 0, . . . , 0] is expected to yield the solution [ , x 1 , . . . , x n ] if approximations are computed with high enough precision.

In this article, we study this last method and apply it to the problem of retrieving polynomial roots in number fields. In particular, under the conjecture that the lattices we consider follow the Gaussian heuristic, we establish a heuristic precision for which one is ensured to retrieve an element, see Theorem 3.17. We note that a similar study has been done in [START_REF] Pellet-Mary | On the Hardness of the NTRU Problem[END_REF] when considering the version solving a SVP instead of a BDD. Following their analysis, we provide in Theorem 3.11 a proven precision ensuring correctness of the decoding, yet larger than the heuristic one.

Additionally, one of our main contribution is to show how to take advantage of a number field extension L/K to replace the decoding of an element in L by the decoding of [L : K] elements in K. We will call it the relative method. When applied to the problem of solving polynomial equations, applying this method comes with the cost of searching through a set of size d [L:K] , where d is the degree of the equation considered.

In order to improve the practical efficiency of our algorithms, we develop several heuristic strategies and observations allowing for substantial speed-ups.

• We describe a modification of the LLL algorithm -called SpecLLL -which improves its running time when B is of the form (1, α, . . . , α n-1 ) : we pre-reduce each new basis vector of index i + 1 using the relation used to size-reduce the previous vector of index i with respect to the lattice generated by the (i -1)-th first rows, see Algorithm 9. Note that this modification was inspired by [START_REF] Plantard | LLL for ideal lattices: re-evaluation of the security of Gentry-Halevi's FHE scheme[END_REF], which is a version of LLL using the specific structure of ideal lattices. Asymptotically, we gain between 20% and 50% in the execution time, depending on which implementation of LLL is tested, as shown in Figure 2 and3. • We provide a tighter evaluation of the precision required to retrieve the coefficients of a targetted element -see Section 5.2.

• We use a early abort strategy in the decoding phase (with Babaï's nearest plane algorithm [START_REF] Babai | On Lovasz lattice reduction and the nearest lattice point problem[END_REF]) to avoid unnecessary computations, see Algorithm 10. This is particularly impactful when using our relative method.

Using our implementation in Gp [START_REF]PARI/GP version 2.11.2[END_REF] 1 , we study the generic behaviour of our algorithms, how our improvements impact their running time, and compare them to the function nfroots implemented in Pari/Gp [START_REF]PARI/GP version 2.11.2[END_REF]. In most of our experiments we consider number fields defined by polynomials whose coefficients are randomly drawn in a given segment. Respectively to this definition of "random number fields", we are then able to study the average behaviour of the aforementioned algorithms.

Concerning the absolute method we can observe the following facts.

• We first remark that our absolute method is more stable than the p-adic algorithm implemented in Pari/Gp. Indeed, there can be as much as 10% of fields over which the execution time of nfroots explodes. From experiments, these are fields for which nfroots do not find a suitable inert prime. Consequently, our algorithm in its certified version has similar running time in average, depending on the parameters, despite being slower than nfroots at its best. • It is more influenced than Pari/Gp nfroots function by several parameters : the dimension [K : Q] and the size of the roots. This is mostly linked to the fact that the lattices we use to decode take longer to be reduced than powers of prime ideals as in nfroots. Our heuristic improvements have significant impact on the time efficiency of our algorithm (10 times faster than the certified version in dimension 100 for example, see Figure 5).

Then when we consider relative extensions L/K and our relative method we have the following main observations:

• the heuristic observations allow us to obtain a more efficient algorithm as well in the relative case: between 10 and 100 times faster for relatively small parameters chosen for our experiments, see Figure 7; • when the relative degree [L : K] and the degree of the equation are relatively small, our relative algorithm can offer significant speed-ups compared to the absolute one: again for small parameters, our relative algorithm can already be up to 10 times faster than the absolute one, see Figure 8 and Figure 9 for example.

Finally we study specific families of number fields, namely cyclotomic fields and real Kummer extensions of the form Q( p √ m 1 , . . . , p √ m r ) with (m 1 , . . . , m r ) ∈ N r and p a prime integer. We can observe the following facts:

• over cyclotomic fields, our relative method applied to the extension

K m /K + m -it has relative degree [K m : K + m ] = 2 -
does not outperforms Pari/Gp nfroots function, which highlights the fact that cyclotomic fields are "good" fields for this method;

• over real Kummer extensions, which are "bad" fields for nfroots, the situation is completely different, and our relative algorithm can be up to 500 times faster than Pari/Gp nfroots function, see Section 6.3.4.

Future work.

First we plan to study the possibility of using the structure of relative extensions within the p-adic method. If we were to be successful, it might be adapted to general global fields as well, which are a natural generalisation of number fields [START_REF] Belabas | Factoring polynomials over global fields[END_REF].

Since the main bottleneck of our method is the reduction of lattices to decode, we plan to improve SpecLLL. One direction would be to follow the strategy described in [START_REF] Kirchner | Towards Faster Polynomial-Time Lattice Reduction[END_REF] for knapsack-like lattices which could lead to smaller running times. Then when there is no subfield, it is possible to adapt the strategy by using several embeddings. Intuitively, adding relations should allow us to decode more easily.

Outline. The rest of this article is as follows. We give necessary recalls on number fields and Euclidean lattices are in Section 2. In Sections 3 and 4 we describe the generic methods considered. Then Section 5 is used to detail the improvements that we developed to speed-up the running time of our algorithms. Finally, we provide experimental results obtained from our implementation in Section 6. We also give additional data in Appendix B.

Recalls on number fields and lattices

In this section, we recall some notions and facts that we will use in the rest of the article. First we will quickly mention number fields, then describe Euclidean lattices and reduction algorithms.

Notations 2.1. The inner product is denoted by (• | •). Given x ∈ R, we denote by {x} its fractional part x -x .

Algebraic closures of number field extensions considered will be designated by Ω. Given a ring morphism σ : A → B and a ∈ A, a σ can be used to design σ(a). This extends to any object f which can be identified to a vector with coefficients in A, such as polynomials in A

[X]. Additionally, if A ⊂ B and f (X) ∈ A[X] we write Z B (f ) the set of roots of f (X) in B.
Given two ordered sets A and B we will denote by A ⊗ B the tensor product of A and B (when it makes sense), i.e. A ⊗ B = {ab, b ∈ B | a ∈ A}. If A and B are not ordered A ⊗ B will be the collection of all the products ab such that a ∈ A and b ∈ B. Finally, we also use this notation for the tensor product of vectors and matrices.

Given a matrix M , we will denote by M [i] its i-th row and M T its transpose. Given a vector v we will write s(v) for log 2 v ∞ . This notation extend to any object that can be expressed as a vector, such as polynomials.

2.1. Number fields. We refer the reader to [START_REF] Belabas | Topics in computational algebraic number theory[END_REF][START_REF] Cohen | Advanced Topics in Computational Number Theory[END_REF]13,[START_REF] Neukirch | Algebraic Number Theory[END_REF][START_REF] Samuel | Algebraic theory of numbers[END_REF] for anything related to number fields and computational number theory.

Definition 2.2.

A number field K is a field which is a finite extension of Q, i.e. a finite dimensional Q-vector space. Notation 2.3. Given an extension L/K of number fields, we will call the dimension of L over K the degree of L/K. It will denoted by [L : K]. Proposition 2.4. Let L/K be an extension of number fields. Then there is an irreducible polynomial

P (X) ∈ K[X] such that L ∼ = K[X] (P (X)) . and [L : K] = deg P (X). Moreover P (X) has [L : K] distinct roots in an algebraic closure Ω of K containing L. These roots define [L : K] distinct K -isomorphisms of L into Ω. If α is such a root,
then the corresponding isomorphism σ α is the following,

σ α : K[X] (P (X)) -→ K[α] ⊂ Ω [L:K]-1 i=0 c i X i -→ [L:K]-1 i=0 c i α i .
Notation 2.5. We call any such polynomial a defining polynomial of L over K, and use denote it by P K (X).

An element σ α ∈ Hom(K, C) is a field embedding of K into C corresponding a root α of P K (X) in C. There are r 1 real embeddings and r 2 pairs of (strictly) complex embeddings. The two elements of a given pair are conjugates one from each other. It is usual to write σ 1 , . . . , σ r1 the real embeddings and to consider that σ j+r2 = σ j for all j ∈ r 1 + 1, r 1 + r 2 .

Definition 2.6 (Minkowski embedding). Given a number field K defined by a degree n irreducible polynomial P (X), the canonical embedding or Minkowski embedding is defined as

(2.1) σ K : K -→ R r1 × C r2 ∼ = R n x -→ (σ i (x)) i∈ 1,r1+r2 .
Then K can be seen as embedded in R n . We will relax this classical definition by considering any algebraic closure Ω instead of C. This way σ K defines an embedding of K into Ω. Then one can define a relative version of the Minkowski embedding: for a field extension L/K we define

σ L/K : x -→ (σ(x)) σ∈Hom K (L,Ω) .
We call this map the Minkowski embedding relative to L/K.

Euclidean lattices.

We refer the reader interested in more in-depth presentations on Euclidean lattices to [START_REF] Micciancio | Complexity of Lattice Problems[END_REF][START_REF] Conway | Sphere Packings, Lattices and Groups[END_REF].

Gram-Schmidt orthogonalisation. An important and classical computation in linear algebra is the Gram-Schmidt orthogonalisation (GSO). It allows transforming a free family of a vector space (with a scalar product) into in an orthogonal family. The naive algorithm can be found in Algorithm 1. For the GSO computation, one can follow a QR decomposition as described in [START_REF] Nguên | Floating-Point LLL Revisited[END_REF] for example which gives an algebraic complexity of O(n 3 ).

Algorithm 1 GSO

Require

: A free family B = {b 1 , .., b r } of R n Ensure: A family B = { b1 , .., bn } with b1 = b 1 and ( bi | bj ) = 0 for i = j 1: B ← B 2: for i = 1 to r do 3: bi ← b i 4: for j = 1 to i -1 do 5: bi ← bi - (b i | bj ) ( bj | bj )

Definition and first properties.

Definition 2.8. A Euclidean lattice is a discrete subgroup of R n where n is a positive integer. We say a lattice is an integral lattice when it is a subgroup of Z n or rational when it is in Q n . A basis of a lattice L is a basis of L as a Z-module. The cardinal of said basis is called the rank of the lattice. Notation 2.9. Given a matrix B we will write L(B) the lattice generated by its row vectors. Definition 2.10. Consider a Euclidean lattice L with basis matrix B. Then the determinant of L, denoted by det(L), is the value det(BB T ).

Notation 2.11. The determinant of a lattice L is also called its volume because it is the volume of the fundamental domain defined by the vectors of one of its bases. Thus it is also written vol(L).

One of the most important problem over lattices is to compute short vectors. In particular, an important quantity is the length of one of the shortest non-zero vector. It is usually denoted by λ 1 (L). We can give a minimal bound of λ 1 using the Gram-Schmidt orthogonalisation of a basis we have at hand. Theorem 2.12.

Let B = (b i ) i∈ 1,r be a basis of a lattice L. Then λ 1 (L) min{ bi | i ∈ 1, r }.
Then one can analyse further the geometry to obtain approximate values on λ 1 .

Heuristic 1 (Gaussian heuristic). Given a lattice L of rank r, an approximate value for λ 1 (L) is

(2.2) λ 1 (L) gauss = r 2πe
× r vol(L).

In our context, the problem that we will be interested in is the Bounded Distance Decoding with it approximate version. Definition 2.13 (BDD: Bounded Distance Decoding). Given a basis B of a lattice L and a point x such that d(x, L) < λ 1 (B)/2, find the lattice vector v ∈ L closest to x. Definition 2.14 (BDD γ : γ-Approximate Bounded Distance Decoding). Given a basis B of a lattice L, a point x and a approximation factor γ ensuring d(x, L) < γλ 1 (B) find the lattice vector v ∈ L closest to x.

In practice, one considers BDD γ for γ < 1 2 . This ensures that there is only one lattice vector v satisfying d(x, v) < γλ 1 (B).

Algorithms for lattices.

Intuitively if a basis B is composed by vectors globally more orthogonal to each other than the vectors of another basis matrix B are, then the vectors of B will be globally shorter than the vectors of B . Therefore, given a basis it is natural to orthogonalise it as much as possible to solve problems on lattices. Since it likely results in a basis with shorter vectors, we call such a process a reduction process or reduction algorithm.

First let us define a weak notion of basis reduction due to Hermite [START_REF] Hermite | Extraits de lettres de M. Ch. Hermite à M. Jacobi sur différents objects de la théorie des nombres[END_REF]. Definition 2.15 (Size-reduce). A basis B = (b 1 , . . . , b r ) of a lattice is said to be size-reduced if its GSO satisfies the following condition: ∀i ∈ 1, r , ∀1 j < i, |µ i,j | 1 2 .

One can find the simple algorithm computing a size-reduced basis in Algorithm 2, which is essentially an approximation of the GSO algorithm (Alg. 1).

Algorithm 2 SizeReduce

Require:

A free family B = {b 1 , .., b k } of L such that |µ i,j | 1/2 for all i = j, an element b / ∈ L. Ensure: An element b k+1 such that b k+1 ≡ b mod L and |µ k+1,i | 1/2 for i = k + 1 1: b k+1 ← b 2: B, G ← GSO(B) 3: for i = k to 1 do 4: b k+1 ← b k+1 - (b k+1 | bi ) bi 2 b j 5:
Update G 6: end for 7: return B ∪ {b k+1 }, G

A fairly natural way of reducing a basis would be to follow Algorithm 1, and replace all coefficients µ i,j by their closest integers. This way one could obtain a basis close to the GSO of the starting matrix, i.e. which is size-reduced. In order to obtain a polynomial time algorithm outputting a basis which is proven to be reduced for varying dimension, one has to introduce a new reduction condition. This is the result of the ground breaking work by A. K. Lenstra, H. W. Lenstra and L. Lovász in [START_REF] Lenstra | Factoring Polynomials with Rational Coefficients[END_REF]. They define a new notion of reduced basis, that is then called LLL-reduced. Definition 2.16. Consider a lattice L defined by a basis B = (b 1 , . . . , b r ) and δ ∈] 1 4 , 1[. Then B is called LLL-reduced with parameter δ (or δ-LLL reduced) if it satisfies the following conditions:

(1) It is size-reduced: ∀i ∈ 1, r , ∀1 j < i, |µ i,j | 1 2 ; (2) It satisfies the Lovász conditions: ∀i ∈ 2, r , δ bi-1 bi + µ i,i-1 bi-1 2 = bi 2 + µ 2 i,i-1 bi-1 2 .
The LLL algorithm shown in Algorithm 3 essentially consists of applying SizeReduce to new vector basis incrementally, verify if Lovász condition is true and continue if so. Otherwise we swap the two last vectors and reduce again.

1) ∀i ∈ 1, r , ∀1 j i, b j 2 (i-1)/2 bi (2) For any x ∈ L \ {0}, b 1 2 (r-1)/2 x .
Theorem 2.17 shows that a LLL reduced basis has good properties. It provides upper bounds related to the norms of the basis vectors. In particular, one can remark that the norm of shortest basis vectors cannot be too large compared to λ 1 (L). Indeed, the second point shows that the LLL algorithm solves in deterministic polynomial time SVP γ , for γ = 2 (r-1)/2 . Many improvements and versions were developed since the original version of LLL. Among many others, one can consider the use of floating-point arithmetic [START_REF] Nguên | Floating-Point LLL Revisited[END_REF].

Algorithm 3 LLL

Require: B, a basis of L of rank r, and a constant δ ∈] 1 4 , 1[. Ensure: B , a δ-LLL reduced basis of L.

1: i ← 2 2: B ← {b 1 } 3: while i r do 4: B ← (b 1 , . . . , b i-1 ) 5: B , G ← SizeReduce(B , b i ) 6:
if Lovász condition is satisfied for δ, i then i ← i + 1 Again the output depends on the quality of the basis given as input. We can prove that the output is not too far from the target given the basis is LLL-reduced. Proposition 2.20. Consider a rank r lattice L, given by a basis B.Then for input t and B, Algorithm 4 outputs v ∈ L lying in t + F( B). Thus it solves BDD γ for γ

v ← v -(v| bi)
1 2 min{ bi | i ∈ 1, r }.
Following [START_REF] Nguyen | An LLL Algorithm with Quadratic Complexity[END_REF], the algebraic complexity of NearestPlane is at most O n 3 + n 2 M .

Absolute method

In this section, we study the methods to recover number field elements from complex embeddings, and how to apply them for solving polynomial equations. Definition 3.1. If x is in R, the approximation of x up to l-bits for l ∈ N is the integer 2 l x . If x ∈ C then its approximation up to l-bits is 2 l (x) + i 2 l (z) . In both cases it is be denoted by [x] l . Remark 3.2. We commonly identify a complex number x with the pair of real numbers ( (x), (x)). We extend this identification to approximations.

3.1. Recovering elements from complex embeddings. First we describe how we compute the coefficients of an element given one of its complex embeddings. Definition 3.3. Consider a number field K, B a Q-basis of K, σ ∈ Hom(K, C), and l ∈ N. We call a basis lattice of K up to precision l relative to B and σ and denote by L(B, σ, l) the lattice generated by the matrix B(B, σ, l) defined as follows:

(3.1) B(B, σ, l) =        -[σ(b 1 )] l C 0 . . . 0 -[σ(b 2 )] l 0 C . . . . . . . . . . . . . . . . . . 0 -[σ(b n )] l 0 . . . 0 C       
The matrix B(B, σ, l) is called the basis matrix of L(B, σ, l).

Remark 3.4.

• When there is no ambiguity regarding K, B or σ, we will simply denote L(B, σ, l) by L l and call it the lattice basis of K up to precision l. Similarly the matrix B(B, σ, l) will be written B l .

• The constant C is used to ensure the validity of the decoding, and acceleratethe reduction algorithm on B l . It will be determined latter.

• If the embedding σ is not a real embedding, then the first column of the matrix in Equation 3.1 is in fact two columns, containing respectively the real and imaginary parts of the corresponding complex numbers. As before, consider K a number field,

B = (b 1 , . . . , b n ) a Q-basis of K, and x ∈ K such that there is (x i ) i∈ 1,n ∈ Z n with x = x 1 b 1 + • • • + x n b n . Now assume that [σ(x)] l is known for some σ ∈ Hom(K, C)
and l ∈ N. Then one can use Babaï's nearest plane algorithm (see Algorithm 4) using L(B, i, l) and t = ([σ(x)] l , 0, . . . , 0). It is also better to reduce B(B, σ, l) with LLL first, and use Algorithm 4 with input this reduced basis and t. This leads to Algorithm 5. Notation 3.6. Given K a number field, B a Q-basis of K, σ ∈ Hom(K, C) and a precision l, we denote by L(B, σ, l) the LLL-reduced basis of B(B, σ, l). Similarly, we will write L l when there is no ambiguity.

The output of Algorithm 5 is a vector of coefficients which are expected to be the coefficients of x in the basis B. The correctness of the outcome depends on the parameters chosen, i.e. the precision l and the constant C. We will determine a lower bound on the precision in Section 3.2, then under a reasonnable conjecture on lattices L l we will exhibit a slightly better lower bound in Section 3.3.

Given x ∈ O K , if one denote by t x the target vector 2 l x σ , 0, . . . , 0 we wish to evaluate a precision l for which e x := NearestPlane(L l , t x ) is equal to [ , Cx 1 , . . . , Cx n ]. It is known that Babaï's nearest plane

Algorithm 5 TestDecode

Require: An integer l, the matrix L l of a reduced basis of L(B, σ, l), [σ(x)] l for some x ∈ K. Ensure: A candidate y = (y 1 , . . . , y n ) for the vector of coefficients of x expressed in B.

1: r ← [K σ : R] r = 1 if σ(K) ⊂ R, and 2 otherwise 2: t ← ([σ i (x)] l , 0, . . . , 0) ∈ Z n+r 3: v ← NearestPlane(t, L l ) (Alg. 4) 4: return [v r+1 , .., v n+r+1 ]/C
algorithm outputs a vector with norm smaller than half the norm of the shortest vector of the GSO. Thus, obtaining a lower bound on the first minimum of L l will allow us to obtain a bound on the norm of the output of NearestPlane(L l , t g ). Coupled with an upper bound on the norm of e g , this will give a condition for a correct decoding, corresponding to

(3.2) e g 2 λ 1 (L l ) 2 n . Proposition 3.7. Consider K a number field, L l = L(B, σ, l) a basis matrix of K, and x ∈ Z[B].
Let m be an integer such that m = 1 if σ(K) ⊂ R and m = 2 otherwise. Then Algorithm 5 outputs the correct vector of coefficients (x 1 , . . . , x n ) of x in B if the following holds:

(3.3) 2 m-1 (1 + x 1 ) 2 4 + C 2 x 2 2 λ 1 (L l ) 2 2 2n .
Proof. In TestDecode we wish to solve the BDD with respect to the lattice L(B, σ, l) and target vector t = ([σ(x)] l , 0, . . . , 0). As Proposition 2.20 states, the output is known to be correct if the distance between the target and the lattice is smaller than 1 2 min bi 2 | i ∈ 1, r . The lattice vector v which is expected to be the closest to

t is v = ( n i=1 x i [σ(b i )], -Cx 1 , . . . , -Cx n ). The error vector e = t -v is then equal to [σ(x)] l - n i=1 x i [σ(b i )], Cx 1 , . . . , Cx n .
Now let us consider the case where m = 1 and look at the first coordinate of e. First write (η, 1 , . . . , n ) ∈ [- 1 2 , 1 2 ] n+1 the vector of errors due to the approximations, i.e. [σ(x)] l = 2 l σ(x) + η and for all

i ∈ 1, n , [σ(b i )] l = 2 l σ(b i ) + i . Then we have e 1 = 2 l σ(x) + η - n i=1 2 l x i σ(b i ) + x i i = η - n i=1 x i i which gives e 2 1 (1 + n i=1 |x i |) 2 /4 = (1 + x 1 ) 2 /4. If m = 2, or equivalently σ(K) ⊂ R, one needs
to consider the real and imaginary parts. Thus we get e ∈ R n+2 and (η,

1 , . . . , n ) ∈ [-1 2 , 1 2 ] n+2 with η = (η 1 , η 2 ). Following the previous analysis we obtain e 2 1 (1 + n i=1 |x i |) 2 × 2/4 = (1 + x 1 ) 2 /2.
Thus we obtain the following upper bound for e

e 2 2 2 m-1 4 (1 + x 1 ) 2 + C 2 x 2 2 .
Finally remark that Theorem 2.17 tells us that a LLL-reduced basis (b 1 , . . . , b n ) of a lattice L (with δ = 3 4 ) satisfies bi

2 2 b1 2 2 /2 n-1 λ 1 (L)/2 n-1 . Notation 3.8. Given x ∈ Z[B]
and C ∈ N * , we will write m x for the upper bound of e x 2 2 , i.e. such that m 2

x :=

2 m-1 (1+ x 1 ) 2 4 + C 2 x 2 2
Now if one has a lower bound for λ 1 (L l ) depending on the parameters, one can deduce a condition for the correctness of the output of TestDecode. In particular it is possible to obtain a lower bound of the precision l for which the computation is correct.

Proven precision and correctness.

Let us determine for which precision Algorithm 5 outputs the correct vector of coefficients. Notations 3.9. Consider a number field K and B a Q-basis of K. Let us write D B for a denominator of B, i.e. such that for all

i ∈ 1, n , D B b i ∈ Z[X] where K ∼ = Q[X]/(P K (X)). Additionnaly we will denote max i∈ 1,n T 2 (b i ) by m(B, T 2 ) .
(3.4) λB l 2 2 l C n-1 n √ n n 2 n(n-1) m n-1 x m(B, T 2 ) n-1 D n B (1 + P K 2 ) 2n-1 .
Proof. We will focus on the case where σ is a real embedding, the proof in the case where σ(K) ⊂ R being almost identical. We follow the proof of [START_REF] Pellet-Mary | On the Hardness of the NTRU Problem[END_REF]Lemma A.7], where similar lattices are considered. A given λ ∈ Z n generates the vector of L l of the form

[- r i=1 λ i (2 l b σ i + bi ), Cλ 1 , . . . , Cλ n ]. If we write s(λ, l) := n i=1 λ i (2 l b i + bi ) then |s(λ, l)| 2 l | n i=1 λ i b σ i | - n i=1 |λi| 2 2 l |λ σ | - λi 1 2
, where λ is seen as an element of K. Then we can write λB l (B)

2 λB l (B) 1 / √ n 2 l |λ σ |/ √ n. Let us find a lower bound for |λ σ |. If µ = D B λ then from [33, Lemma A.8] we have (3.5) |µ σ | 1 n(1 + P K 2n-1 2 )T 2 (µ) n-1 . Then T 2 (µ) = T 2 (D B n i=1 λ i b i ) D B n i=1 |λ i |T 2 (b i ) D B m(B, T 2 ) λ 1 , so Equation (3.5) gives |λ σ | 1 n λ n-1 1 D n B m(B, T 2 ) n-1 (1 + P K 2 ) 2n-1
.

Finally, recalling that we consider λ ∈ B(0, 2 n m x /C) and that λ 1 √ n λ 2 we get the following lower bound for λ 1 (L l )

λ 1 (L l ) 2 l C n-1 n √ n n 2 n(n-1) m n-1 x D n B m(B, T 2 ) n-1 (1 + P K 2 ) 2n-1 .
Theorem 3.11 (Proven precision for correctness).

Consider K a number field, B a Q-basis of K and x ∈ Z[B]. Additionally fix σ ∈ Hom(K, C), C ∈ N, and m ∈ N such that m = 1 if σ(K) ⊂ R and m = 2 otherwise. If l ∈ N with l 1 satisfies l n 2 + (n + 1) log 2 C + n log 2 x 2 + 3 log 2 (n) 2 + log 2 D B + 2 + (n -1) log 2 m(B, T 2 ) + (2n -1) log 2 P K 2 (3.6)
then Algorithm 5 outputs the vector of coefficients of x in the basis B. In particular, the coefficients of x given one of its embedding can be recovered in time polynomial with respect to the size of the entries.

Proof. Using Equations (3.2) and (3.5) we can conclude that the decoding is correct if

2 n m x 2 l C n-1 n √ n n 2 n(n-1) m n-1 g D n B m(B, T 2 ) n-1 (1 + P K 2 ) 2n-1 which is equivalent to 2 l 2 n m n x n √ n n 2 n(n-1) D n B m(B, T 2 ) n-1 (1 + P K 2 ) 2n-1 C n-1 which is verified as soon as l n 2 + n(log 2 (m x ) + log 2 (n)/2 + log 2 D B ) + (n -1)(log 2 m(B, T 2 ) -log 2 (C)) + (2n -1) log 2 (1 + P K 2 ).
Now we can replace m x by its value. However let us first rewrite it for simplicity, using x 2 only.

Since

x 1 √ n x 2 , one can safely replace m 2 x by 2 m-1 (1+ √ n x 2 ) 2 4 + C 2 x 2 2 = x 2 2 (C 2 + 2 m-1 4 (n + 2 √ n/ x 2 + 1/ x 2 2 )) x 2 2 (C 2 + 2n) Replacing m 2
x by this last value we get that e g is equal to some [ , Cg 1 , . . . , Cg n ] as soon as

l n 2 + n log 2 x 2 + 3 log 2 (n) 2 + log 2 (C) + log 2 D B + 2 + (n -1) log 2 m(B, T 2 ) + (2n -1) log 2 P K 2 + log 2 C,
which gives the claimed inequality.

Remark 3.12.

If B is an integral basis of O K then one can bound D B by n n √ n P K 2(n-1) 2 [26]. Ad- ditionally if B is LLL-reduced for the T 2 -norm, we have that m(B, T 2 ) D O(1) K [33] so Equation (3.6) becomes l n 2 + n log 2 g 1 + log 2 (n) 2 + (n + 1/2) log 2 n + (n -1)O(1) log 2 D K + (n + 1)(2n -1) log 2 P K 2 + log 2 C.
In the case where B is a power basis, i.e. B = (1, α, . . . , α n-1 ) we have

D B D n-1 α and m(B, T 2 ) = √ n max σ |α σ | n-1 so Equation (3.6
) can be replaced by

l n 2 + (n + 1) log 2 C + n log 2 x 2 + 3 log 2 (n) 2 + (n -1) log 2 D α + 2 + (n -1) 2 log 2 max σ |α σ | + (n -1) log 2 n 2 + (2n -1) log 2 P K 2 .

Heuristic precision and correctness.

Let us now determine a lower bound under a conjecture regarding lattices of the form L l we handle. First we determine the determinant of said lattices.

Lemma 3.13 (Matrix determinant lemma [START_REF] Franklin | Matrix theory[END_REF]). Let A be a ring, M ∈M n (A) be an invertible matrix and U, V ∈ M n,m (A). Then the following is true:

(3.7) det(M + U V T ) = Id m + V T M -1 U det(M ).
Lemma 3.14. Let K be a number field and L l = L(B, σ, l) be a basis lattice of K. Also let m be an integer equal to 1 if σ is real, and 2 otherwise. Then

(3.8) vol(L l ) 2 = C 2n det Id m + 1 C 2 σ(B) T l σ(B) l Proof. By definition vol(L l ) 2 is the determinant of the matrix B(B, σ, l)B(B, σ, l) T = C 2 Id n + σ(B) l × σ(B) T l .
Then Lemma 3.13 gives the claimed identity.

One can deduce from Lemma 3.14 a lower bound on the volume of L(B, σ, l) which depends on the precision l and the size of σ(B).

Notation 3.15. Consider a number field K, B a Q-basis of K, σ ∈ Hom(K, C) and l ∈ N. Let us define the value ∆(B, σ, l). If σ(K) ⊂ R we set ∆(B, σ, l) = σ(B) 2 2 -σ(B) 1 /2 l , and if σ(K) ⊂ R we set ∆(B, σ, l) = (σ(B)) 2 2 + (σ(B)) 2 2 - (σ(B)) 1 /2 l - (σ(B)) 1 /2 l .
Proposition 3.16. Let K be a number field and L l = L(B, σ, l) be a basis lattice of K. Also let m be an integer equal to 1 if σ is real, and 2 otherwise. Then the following is true,

(3.9) vol(L l ) 2 C 2n 1 + 2 2l C 2 ∆(B, σ, l) .
Proof. From Equation 3.8 we can write for m = 1

vol(L l ) 2 = C 2n 1 + 1 C 2 σ(B) l 2 2 = C 2n 1 + 1 C 2 n i=1 [σ(b i )] 2 l . Then for each i ∈ 1, n , there is i ∈ [-1 2 , 1 2 ] such that [σ(b i )] l = 2 l σ(b i ) + i . Thus we obtain vol(L l ) 2 = C 2n 1 + 1 C 2 n i=1 (2 l σ(b i ) + i ) 2 = C 2n 1 + 2 2l C 2 n i=1 (σ(b i ) 2 + 2σ(b i ) i 2 l + 2 i 2 2l ) .
Since for all i ∈ 1, n , one has

| i | 1 2 , we obtain the inequality vol(L l ) 2 C 2n 1 + 2 2l C 2 n i=1 (σ(b i ) 2 -2 × 1 2 × |σ(b i )| 2 l ) . If σ(K) ⊂ R then from Equation 3.8 we have vol(L l ) 2 = C 2n det Id 2 + 1 C 2 σ(B) T l σ(B) l . If we write M = Id 2 + 1 C 2 σ(B) T l σ(B) l , then M =    1 + (σ(B) l ) 2 2 C 2 ( (σ(B) l ) | (σ(B) l )) C 2 ( (σ(B) l ) | (σ(B) l )) C 2 1 + (σ(B) l ) 2 2 C 2    so we get det(M ) =1 + (σ(B) l ) 2 2 C 2 + (σ(B) l ) 2 2 C 2 + (σ(B) l ) 2 2 (σ(B) l ) 2 2 C 4 - ( (σ(B) l ) | (σ(B) l )) 2 C 4 .
By Cauchy-Schwarz inequality we have

(σ(B) l ) 2 2 (σ(B) l ) 2 2 C 4 - ( (σ(B) l ) | (σ(B) l )) 2 C 4 0, therefore vol(L l ) 2 C 2n 1 + (σ(B) l ) 2 2 C 2 + (σ(B) l ) 2 2 C 2 .
Following the same reasoning that we did for the real case, we can conclude that

(σ(B) l ) 2 2 C 2 2 2l C 2 (σ(B)) 2 2 - (σ(B)) 1 2 l and (σ(B) l ) 2 2 C 2 2 2l C 2 (σ(B)) 2 2 - (σ(B)) 1 2 l ,
which gives the desired result.

It is now possible to certify the correctness of the decoding. The Gaussian heuristic provides an estimation of λ 1 (L l ), which can be used to obtain a heuristic condition for the correctness of the algorithm, as in Theorem 3.17. Theorem 3.17 (Correctness of decoding).

Consider K a number field, B a Q-basis of K and x ∈ Z[B]. Additionally fix σ ∈ Hom(K, C), C ∈ N, and m ∈ N such that m = 1 if σ(K) ⊂ R and m = 2 otherwise. If l ∈ N with l 1 satisfies (3.10) l n 2 + n log 2 x 2 + n 2 log 2 (2πe( 1 n + 2)) + log 2 (C) - log 2 ∆(B, σ, l)
2 then Algorithm 5 outputs the vector of coefficients of x in the basis B, if L(B, σ, l) satisfies the Gaussian heuristic (eq. 2.2).

Proof. Let us fix l ∈ N. The Gaussian heuristic states λ 1 (L) ∼ n 2πe det L 1/n . Then one can combine Equation (3.3) to obtain a conditional inequality. In order to simplify the expression, we will replace m 2 x by x 2 2 (C 2 + 2n) as explained in the proof of Theorem 3.11. This leads to the following inequality:

x 2 2 (C 2 + 2n) 1 2 2n n 2πe C 2 n 1 + 2 2l C 2 (∆(B, σ, l)) .
We can obtain the condition

(3.11) x 2 2 (C 2 + 2n) n 2πe C 2 n 2 2l C 2 (∆(B, σ, 1)) .
Under the logarithmic map, the left side of Equation (3.11) gives 2 log 2 x 2 + 2 log 2 (C) + log 2 (1 + 2n C 2 ) while the right side becomes log 2 ( n 2πe )-2n+ 1 n ×(2(n -1) log 2 (C) + 2l + log 2 (∆(B, σ, l))) , and combining them allows us to retrieve the claimed condition.

On can remark that Theorem 3.17 gives a better condition than the theoretical one given by Theorem 3.11. Remark 3.18. As a matter of fact, correctness of decoding is ensured by Equation (3.10) as long as

L l satisfies λ 1 (L l ) λ 1 (L l ) gauss .
In order to estimate the correctness of the value given by Theorem 3.17, we verified if the Gaussian heuristic holds for lattices L l . We computed the average value of the quotient λ 1 (L l )/λ 1 (L l ) gauss for increasing values of l, over random number fields K with fixed degrees. Here "random" means defined by integral polynomials whose coefficients are drawn uniformly in -2 s , 2 s for randomly chosen 1 s 10. The results can be found in Figure 1. One can see that λ 1 (L l ) is larger than the value predicted by the Gaussian heuristic. This tends to show that asymptotically, one can safely consider that Theorem 3.17 provides a correct value certifying the correctness of the output of TestDecode. Note that running this kind of experiment for large dimensions (say larger than 120) would be intractable. Indeed, even approximating λ 1 (L) is a hard problem.

Heuristic 2 (Gaussian heuristic for bases lattices). Consider

K a number field, B a Q-basis of K, σ ∈ Hom(K, C) and l ∈ N. Then λ 1 (L(B, σ, l)) λ 1 (L l ) gauss . (a) σ(K) ⊂ R (b) σ(K) ⊂ R Figure 1. Average value of λ 1 (L l )/λ 1 (L l ) gauss plotted against the precision l, for several n = [K : Q].
3.4. Computing polynomial roots. We described which lattice we use, and the decoding method.

Obviously the reduced matrix L(B, σ, l) is computed once and used to retrieve all roots. Therefore we have the following main steps:

(1) fix an embedding σ : K → C;

(2) compute a precision l ∈ N ensuring that the decoding is correct;

(3) compute a LLL-reduced basis L l of the lattice generated by the basis of K;

(4) using σ, compute approximations of the roots of f (T ) up to a precision l;

(5) use L l to retrieve the roots of f (T ) using TestDecode.

We will call PrecisionEvaluation the function returning the needed precision for input f (T ) ∈ K[T ]. Following Theorem 3.17, it depends on the Euclidean norms of the roots of f (T ). In order to evaluate an upper bound of these norms, we can follow [START_REF] Belabas | A relative van Hoeij algorithm over number fields[END_REF]. We will denote by FloatPolynomialRoots the procedure computing the real (resp. complex roots) of a real (resp. complex) polynomial. We obtain Algorithm 6 describing the method we implemented to compute Z K (f ).

Following the results from the previous section, one can state the following theorem.

Theorem 3.19. Consider a number field K, B a Q-basis of K and f (T ) ∈ K[T ] such that Z K (f ) ⊂ Z[B]. Then for input (K, B, f (T )), Algorithm 6 outputs Z K (f ) in polynomial time.
Finally we give a broad estimate of the algebraic complexity in function of the precision required to ensure correctness. We will only count the complexity linked to lattices operations, as other steps are negligeable. Note as well that we express these complexities in terms of the precision at which computations are made instead of the size of the roots since the latter is unknown. Additionnaly this allows us to take into account different choices for PrecisionEvaluation. Proof. Recall by Theorem 2.18 the algebraic complexity of LLL is in O(n 4 M + n 3 M 2 ), where M is an upper-bound on the bit size of basis elements. A broad estimate of M for B(B, σ, l) is l. For the GSO

Algorithm 6 AbsoluteRoots

Require:

A number field K, f (T ) ∈ K[T ], B a Q-basis of K such that Z K (f ) ∈ Z[B]. Ensure: The set Z K (f ) 1: σ ← ChooseEmbedding(K) 2: l ← PrecisionEvaluation(f (T )) 3: L l ← LLL(B(B, σ, l)) 4: Z ← FloatPolynomialRoots(f σ , l) 5: S ← ∅ 6: for z ∈ Z do 7: y ← TestDecode(L l , z) 8: if f (y) = 0 then 9: S ← S ∪ {y} 10:
end if 11: end for 12: return S computation, we can follow a QR decomposition as described in [START_REF] Nguên | Floating-Point LLL Revisited[END_REF] for example which gives a complexity of O(n 3 ). Finally Algorithm 6 makes d = deg f (T ) calls to Algorithm 4, adding up to O(dn 2 ) .

Relative method

Let us now describe a method to recover the roots of a polynomial in an extension of number fields L/K, which is one of our main contribution.

K (L, Ω) on E is known. Then σ L/K sends K n into Ω n , σ L/K : K n -→ Ω n (x i ) i∈ 1,n -→ ( n i=1 x i σ(e i )) σ∈Hom K (L,Ω) .
Thus given knowledge of σ L/K (x) one can apply σ -1 L/K and obtain recover (x i ) i . For computational purposes, we need to consider embeddings into C n . In order to do so, one needs to fix τ an embedding of K into C then consider σ L/K as the collection of complex embeddings of L extending τ . This leads to Algorithm 7 which retrieves coefficients of x knowing its Minkowski embedding relative to L/K. Lemma 4.1. Algorithm 7 runs in polynomial time and outputs the correct vector of coefficients provided l is large enough.

Proof. The polynomial running time is clear. For any σ : L → C extending τ , its action on x ∈ L can be seen as n i=1 τ (x i )σ(e i ). This way, K is identified with a subfield of C and L is identified with τ (K) n . The action of σ L/K can be expressed as an action from τ (K) n into C n as a matrix in M n (C), that is Σ L/K . In particular we have

Σ L/K [i] = σ L/K (e i ), thus XM = XΣ -1 L/K = (x τ 1 , . . . , x τ [K:Q] )
. Thus knowing approximations of σ L/K (x) and Σ L/K up to l + s, it is possible to find the approximations of (τ (x i )) i

Algorithm 7 Mink2coeff

Require: An extension L/K, given by B a basis of K and E a K-basis of L, M = Σ -1 L/K the matrix of σ -1 L/K expressed with respect to τ (E) up to a precision l + s, the matrix L l from a reduced basis of L(B, τ, l) for some τ ∈ Hom(K, C) and X = [σ L/K (x)] l+s for some x ∈ L/K. Ensure: A candidate y = (y 1 , . . . , y N ) for the vector of coefficients of x expressed in B ⊗ E.

1: Y ← XM 2: y = [ ] 3: for i = 1 to n do 4: y ← [y | TestDecode(L l , Y i )]
Concatenation of row vectors 5: end for 6: return y up to l. Then by the results of Sections 3.2 and 3.3 we know that TestDecode(L l , [x i ] l ) is the vector of coefficients of x i with respect to B provided that l is large enough.

4.2.

An algorithm for polynomial roots. We can apply the previous strategy to compute polynomial roots by decoding in the subfield K. Again, we fix some objects. The extension of number fields L/K is given by a Q-basis B and E a K-basis of L. Then consider a polynomial

f (T ) ∈ L[X] such that Z L (f ) ⊂ Z[E ⊗ B].
From what we described previously, in order to retrieve the coefficients of x ∈ Z L (f ), one can compute σ L/K and use Mink2coeff with the following main steps:

(1) compute a precision l certifying the correctness of the computation;

(2) compute L l a LLL reduced basis of L(B, τ, l);

(3) compute M = Σ -1 L/K up to precision l + s for some s; (4) compute Z = σ∈Hom K (L,C) Z C (f σ ) up to precision l + s;

(5) For each x ∈ Z, use Mink2coeff to obtain a root candidate. This leads to Algorithm 8.

Remark 4.2. The set Z is the cartesian product of the sets Z(f σ ) with σ in Hom K (L, C). Each of such set Z(f σ ) has at most d = deg f elements. Therefore, Z is a set of at most d n complex numbers. Moreover one cannot tell a priori if an element z ∈ Z(f σ ) is of the form [σ(x)] l+s for some x ∈ Z L (f ), or even if a vector (z 1 , . . . , z n ) ∈ Z corresponds to a root x of f (T ). Thus one has to call Mink2coeff d n times in the worst case. Even if f (T ) splits in L, this leads to a search of d vectors in a set of size d n . In order to improve slightly this search, a simple observation can be made. Let us write Z = σ Z C (f σ ) where σ ranges over Hom K (L, C). Then one has

(4.1) ∀x ∈ Z K (f ), ∀σ ∈ Hom K (L, C), ∃!z ∈ Z C (f σ ) | z = [σ(x)] l ,
which implies that once we found a correct vector in Z we can remove from the search tree all the nodes where any of its coordinates appears. A more precise study of the average cost of the search (number of vectors of Z tested) can be found in Appendix A.

Notation 4.3. We denote by UpdateTree the procedure updating the search space as described.

The absolute method AbsoluteRoots requires at most d = deg f (T ) decodings, while RelativeRoots naive requires enumerating through d n vectors, corresponding to n decodings each. The mere enumeration of d n elements shows that RelativeRoots naive has an exponential cost when n increases. In addition, several operations on vectors and matrices are done for each of the d n possibilities. Thus it is quickly impractical.

Algorithm 8 RelativeRoots naive

Require: An extension L/K, given by B a basis of K and E a K-basis of L, and

f (T ) ∈ L[T ] such that Z L (f ) ∈ Z[E ⊗ B] Ensure: Z L (f ) 1: l ← PrecisionEvaluation(f (T )) 2: L l ← LLL(B(B, τ, l)) 3: M ← Σ -1 L/K Up to precision l + s 4: Z ← σ∈Hom K (L,C) FloatPolynomialRoots(f σ , l + s) 5: S ← ∅ 6: for z ∈ Z do 7: y ← Mink2coeff(z, M, L l )
Compute the inverse and decode UpdateTree(Z, z)

11:
end if

12: end for 13: return S However, for small n, Algorithm 8 can considerably speed-up the computation of Z K (f ). Indeed one has to remember that an important part of the computation time is dedicated to the reduction of the lattice used to decode, as is also the case for the algebraic method. Algorithm 6 requires the reduction of a lattice of rank [L : Q], while the rank of the lattice reduced in Algorithm 8 is [L : Q]/n. In addition, the precision needed to certify the computation shown in Theorem 3.17 involves the dimension. Therefore, dividing the dimension allows us to do computations at a smaller precision, which also leads to smaller coefficients in the matrix B l which is reduced.

Theorem 4.4. Consider an extension

L/K, B a Q-basis of K, E a K-basis of L and f (T ) ∈ L[T ] such that Z L (f ) ⊂ Z[E ⊗ B].
Then for input (L/K, E, B, f (T )), Algorithm 8 outputs Z L (f ) in polynomial time, except eventually for the enumeration due to the for loop.

Proof. Since the required precision to ensure correctness of decoding has been proved to be polynomial with respect to entry sizes, the polynomial time complexity of each intermediate operations is clear. For the correctness, remark that for any x ∈ Z L (f ) and any σ ∈

Hom Q (L, C), σ(x) is a root of f σ . Thus, σ L/K (x) ∈ σ∈Hom K (L,C) Z C (f σ ), so for each x ∈ Z L (f ) there is one vector of Z in Algorithm 8 which is of the form ([σ(x)] l+s ) σ = [σ L/K (x)
] l+s . This ensures that S is the correct set at the end of Algorithm 8.

Proposition 4.5. Consider an extension

L/K, B a Q-basis of K, E a K-basis of L and f (T ) ∈ L[T ] such that Z L (f ) ⊂ Z[E ⊗ B].
Then for input (L/K, E, B, f (T )), the algebraic complexity of lattice operations of Algorithm 8 (reduction of a basis lattice L l , GSO computation and decoding) are respectively in O(n 4 K l+ n

3 K l 2 ), O(n 3 K ) and n L/K d n L/K O(n 2 K )
, where l is the required precision.

Proof. The proof is similar to the one of Proposition 3.20, noting that the lattice used to decode is linked to K, that there are d n L/K elements in Z and that Mink2coeff makes n L/K calls to TestDecode for each of these elements.

l + n 3 K l + n L/K d n L/K n 2 K )
for Algorithm 8. Thus, we obtain a condition for a trade-off :

n 2 K (n 2 K l + n K l + n L/K d n L/K ) = n 2 L (n 2 L l + n L l + d) ⇐⇒ n L/K d(d n L/K -1 -n L/K ) = n K l(n 3 L/K (n L + 1) -(n K + 1)). (4.2)
Using Equation (5.6) allows us to obtain a broad indication on which algorithm to run. For example, fixing [L : K] = n L/K = 2 we obtain 2d(d -2) n K l(15n K + 7), therefore our relative algorithm would be advantageous for d up to (at least) n K l(15n K +7) 2 . Note that following both theoretical and heuristic bounds from Theorems 3.11 and 3.17, l is larger than

n 2 L + n L log 2 x 2 so n K l(15n K +7) 2 can be replaced by n K (2n K (2n K + log 2 x 2 ))(15n K + 7) 2 = n K (2n K + log 2 x 2 )(15n K + 7).

Improvements and heuristic observations

In order to improve the naive algorithms presented in Sections 3 and 4, several directions can be explored. The main bottleneck of our absolute method (Alg. 6) is the reduction of a basis lattice L(B, σ, l). It can be hasten by improving the reduction process itself or by evaluating the required precision l more accurately. Our relative method potentially requires many decodings, i.e. calls to a BDD solver such as NearestPlane (Algorithm 4). Therefore, improving this step can speed-up considerably the running time of Algorithm 8.

Basis reduction in the case of power-bases.

The first heuristic improvement that we develop concern the reduction of B(B, σ, l), in the case where B is a power-basis, i.e there is α ∈ K such that B = (1, α, . . . , α n-1 ). The idea behind the improvement comes from the following observation. First, denote by B (i) the top left i × (i + 1) submatrix of B, then assume that B is reduced up to the i-th vector, i.e. we found U (i) such that

L (i) = U (i) B (i) is reduced. Then we found u (i) ∈ Z i such that u (i) B (i) = L (i) [i].
Consider now the (i + 1)-th vector of the matrix. Then [0,

u (i) ]B (i+1) ≈ αu (i) B (i) = αL (i) [i].
Thus applying the transformation operated to reduce the i-th vector should pre-reduce the (i + 1)-th vector. This leads to Algorithm 9, which computes a LLL-reduced basis L l . Note that pre-reduction strategies have already been mentioned or used in the literature [START_REF] Stehlé | Floating-Point LLL: Theoretical and Practical Aspects[END_REF][START_REF] Kirchner | Towards Faster Polynomial-Time Lattice Reduction[END_REF]. To the best of our knowledge these apply to general knapsack-like matrices, while our observation tries to take advantage of the regularity of the basis vectors, and can be compared to [START_REF] Plantard | LLL for ideal lattices: re-evaluation of the security of Gentry-Halevi's FHE scheme[END_REF].

We compared SpecLLL with LLL for available implementations of Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF], Pari/Gp [START_REF]PARI/GP version 2.11.2[END_REF] and

Fplll [START_REF] Vallée | Fplll, a lattice reduction library[END_REF]. The results can be found in Figure 2 for the real case and Figure 3 for the complex one. The first observation is that SpecLLL is asymptotically faster than LLL, regardless of the software used. Then one can remark that the ratio is decreasing when both the precision or the dimension is increasing.

SpecLLL is always more efficient than LLL when used in Pari/Gp or Magma, with a asymptotic gain of 25% and 35% respectively. For Fplll, using Algorithm 9 results in larger running times for small

Algorithm 9 SpecLLL

Require: B, a basis of a lattice L of rank n. Ensure: B , a LLL reduced basis of L.

1: B ← {b 1 } 2: for i = 2 to n do 3: b i ← b i + b i-1 2 2 e i+1
M is a large constant to ensure reduction

4: b i ← b i -[0, u (i-1) ]B (i)
Pre-reduction using the previous vector precision. However, it becomes more efficient as precision increases and offers speed-ups between 25 and 50% for l = 20000, depending on the dimension. Moreover, as expected the speed-up given by SpecLLL is larger when σ(K) ⊂ R, however one still gains up to 20% when σ(K) ⊂ R.

Note that the gain really depends on the version of LLL used. However, a better gain does not imply that the corresponding software should be used. Indeed, one should also take into account the initial running time of LLL. For example, Fplll is more efficient than the two other implementation. We refer the reader to the timings plots presented in Appendix B.1, where are shown the corresponding timings.

Finally we verified that our modified algorithm really takes advantage of the special shape of the initial matrix. To do so, we launched SpecLLL over matrices of the shape

       β 1 C 0 . . . 0 β 2 0 C . . . . . . . . . . . . . . . . . . 0 β n 0 . . . 0 C       
, where β i are random integers with the same size as the entries of B(B, σ, l), and computed the same timings ratios. Results can be found in Table 6, and one can remark that it is always close to 1, sometimes larger.

Heuristic precision evaluation.

The second observation concern the precision needed to retrieve the roots. First we study which precision is required to retrieve an element depending on its norm, then we present an improvement concerning the evaluation of the norm of the roots.

5.2.1.

Precision from the norm. The precision given by Equation (3.10) allows us to certify the correctness and the polynomial complexity of the method we described. However, it is possible to find a smaller value which is experimentally sufficient to retrieve an element. Fix K a number field given by an irreducible polynomial

P K (X) ∈ Z[X]. Given B = (b 1 , . . . , b n ) a Q-basis of K, we generated random elements x ∈ Z[B] such that for all i ∈ 1, n , x i ∈ -2 s , 2 s
for s ∈ {1, 25, 50, 75, 100}. Then we computed the quotient q t of the precision required to retrieve the coefficients of x by l t = [K : Q] log 2 x 2 .

We chose to test the experimental precision against l t for several reasons. First, when K and B are fixed, it is the term of Equation 3.10 which is asymptotically relevant. Moreover the algebraic method of [START_REF] Belabas | A relative van Hoeij algorithm over number fields[END_REF] requires the norm N K/Q (p k ) to be greater than a value which is essentially l t , so that the decoding is certified. Finally, this value was also suggested by experiments when we first used this method to compute cube roots in multicubic fields [START_REF] Lesavourey | Short Principal Ideal Problem in multicubic fields[END_REF]. When comparing this value to Equation (3.10), we can remark that we gain essentially n(n -log 2 (n)).

Experimentally, the quotient q t seems to be influenced by the size of the elements to decode and the dimension. More precisely, the maximum of the retrieved quotients in our experiments approaches 1 from above when the precision is increasing. Moreover, it seems to increase with the dimension. With these requirements in mind, we observed that it is always smaller than 1 + ln(n) ln ln(n)/(s ln(2) + ln(n)/2)see Figure 16 in appendix. Remark that the quotient in the previous value is the norm of an element with all coefficients equal to 2 s .

If Prec is the precision required to retrieve the coefficients of an element x, it seems reasonable that (5.1)

Prec(x) 1 + ln(n) ln ln(n) s + ln(n)/2 n ln x 2 n ln x 2 + n ln(n) ln ln(n).

Norm of the roots. Fix the factorisation of

f (T ) over K as f (T ) = g(T )h(T ) such Z K (g) = Z K (f ), Z K (h) = ∅.
We can follow [START_REF] Fieker | On Reconstruction of Algebraic Numbers[END_REF][START_REF] Belabas | A relative van Hoeij algorithm over number fields[END_REF] to bound x

2 2 for x ∈ Z K (f ) given f (T ): (1) find B f,T2 such σ K/Q (x) 2 2 B f,T2 for all x ∈ Z K (f ); (2) compute B σ -1 K the matrix norm of σ -1
K , expressed relatively to the canonical basis of σ K/Q (K) and B;

x i σ(b i ) 2 n i=1 |x i σ(b i )| 2 x 2 2 σ(B) 2 2 .
Therefore for any x ∈ K and any σ ∈ Hom(K, C),

x 2 2 |σ(x)| 2 σ(B) 2 2
. We define the function HeuristicNorm as the maximum of such quotients, as follows. For any σ ∈ Hom(K, C), let B f,σ be such that

(5.2) ∀x ∈ Z K (f ), |σ(x)| 2 B f,σ .
Then we fix

(5.3) HeuristicNorm(f ) := max B f,σ σ(B) 2 2 | σ ∈ Hom(K, C) .
Even if HeuristicNorm gives a value which is a lower bound on x 2 2 instead of an upper bound, it allows a first precision to be obtained. This evaluation is usually smaller than B f and gives a good starting point, i.e. we do not need to increase much the precision to retrieve at least some roots.

We evaluated the generic difference between the proper maximal norm of x ∈ Z K (f ) and the value given by HeuristicNorm, and plotted the results in Figure 4. These expiremental values tend to show (5.4) ln M (f ) HeuristicNorm(f ) + ln(n)/2. end if 9: end for 10: return w, true 5.3. Solution testing through finite fields. An important step -especially when using heuristic observations -is to verify that a candidate is indeed a solution (steps 8 of both Algorithm 6 and Algorithm 8). When manupilating large elements, evaluating the polynomial expression f (x) can be costly. Thus we chose to use a probabilistic method, which is summed up as follows:

• choose prime integers p 1 , . . . , p r • check whether f (x) = 0 mod p i for all i ∈ 1, r If the p i are uniformly drawn as 32-bits integers and f (x) is uniformly distributed in F pi , then the probability x of obtaining a false positive is 1/2 32r , which is rapidly small. This choice is particularly useful for our relative method, since it potentially requires to test a huge amount of elements.

Early abort in decoding.

The final observation that we use to speed-up computations consists in improving the decoding step, especially when the tested complex number y does not correspond to any solution. Here is the rationale behind our technique. If the vector Y given to NearestPlane correspond to a solution, then it is expected to be close to a vector of the lattice L l . However, if the vector is not a solution vector, then it should be "far" from a lattice vector. It can even be expected to be uniformly distributed modulo L l . Given a vector t and B a basis, if we denote

|(t | bi )/ bi 2 2 | by λ i , then the distance between v and NearestPlane(t, B) is r i=1 |{λ i }| • bi 2 . The quantity {λ i } ∈ [-1/2, 1/2], thus
we distinguish between two cases : if |{λ i }| 1/4 we deem λ i to be acceptable and we continue the algorithm, while if |{λ i }| > 1/4 we deem t to be rejected. This gives Algorithm 10.

Additionally to this strategy, we will reject a vector of complex numbers during the search of Algorithm 8 as soon as one of the decoding fails.

We checked the experimental maximum number of steps done in Algorithm 10 over bad vectors t of the form [z, 0 . . . , 0], when z ∈ Z C (f ) in the run of Section 5.5, for several root sizes s Z = max x∈Z K (f ) s(x), field dimesion [K : Q] and coefficient sizes of the defining polynomial s(P K ). For fields dimension between 25 and 125 and various root sizes, the maximum that we find is 7. Over all parameters this maximum does not seem to vary much and is mainly in 4, 7 , see Table 1 for example.

Algorithm 11 AbsoluteRootsHeur

Require

: A number field K, f (T ) ∈ K[T ], B a Q-basis of K such that Z K (f ) ∈ Z[B]. Ensure: The set Z K (f ) 1: σ ← ChooseEmbedding(K) 2: l ← HeuristicPrecision(f (T ))
Heuristic norm evaluation and precision formula

3: L l ← LLL(B(B, σ, l))
Use of SpecLLL when B is a power-basis One can remark that the average value is always smaller than 3.

Heuristic algorithms.

All the observations and strategies mentioned above lead to heuristic versions of the algorithms computing polynomial roots. First is the heuristic version of the decoding method TestDecode using EarlyAbortNP. We will design it by TestDecodeHeur. Using this version of the decoding method, together with the heuristic precision evaluation given by Equation (5.5) leads to a heuristic version of Algorithm 6 described in Algorithm 11.

Finally, regarding the relative method, we get a heuristic variant of Algorithm 7 and Algorithm 8. Remark that in Algorithm 12 (thus in Algorithm 13 as well) the use of early abort for the decoding of each coordinate respectively to L/K (step 8 of Algorithm 12) leads generally to decode only one of them when the vector of complex numbers X is not of the form σ L/K (x) (as a matter of fact, the decoding will typically abort only after a few steps). 5.5.1. Trade-off. Now let us express some broad trade-off between our heuristic absolute and relative methods, again considering only computations linked to lattice reduction and decoding. Compared to the previous analysis, we need to take into account the influence of early abort. This still gives O(n 4 L l + n 3 L l + dn 2 L ) in the worst-case for Algorithm 11 while these operations amount to O(n 4 K l + n 3 K l +

Algorithm 12 EarlyAbortMink2Coeff

Require: An extension L/K, given by B a basis of K and E a K-basis of L, an integer l, the matrix L l from a reduced basis of L(B, τ, l), M = Σ -1 L/K up to a precision l + s, and X = [σ L/K (x)] l+s for some x ∈ L/K Ensure: A candidate y = (y 1 , . . . , y N ) for the vector of coefficients of x expressed in B ⊗ E

1: Y ← XM 2: y = [ ] void vector 3: for i = 1 to n do 4: v, b ← TestDecodeHeur(L l , Y i ) 5: if b = false then 6:
return X, b 7:

end if 8: y ← [y | v]
9: end for 10: return y, b

Algorithm 13 RelativeRootsHeur

Require: An extension L/K, given by B a basis of K and E a K-basis of L, and

f (T ) ∈ L[X] such that Z L (f ) ∈ Z[E ⊗ B] Ensure: Z L (f ) 1: l ← HeuristicPrecision(f (T )) 2: L l ← LLL(B(B, τ, l))
Use of SpecLLL when B is a power-basis

3: M ← Σ -1 L/K Up to precision l + s 4: Z ← σ∈Hom K (L,C) FloatPolynomialRoots(f σ , l + s) 5: S ← ∅ 6: for z ∈ Z do 7: y, b ← EarlyAbortMink2coeff(z, M, L l ) Early abort 8:
if b and f (y) = 0 then Verification through finite fields 9:

S ← S ∪ {y} 10:

UpdateTree(Z, z)

end if

12: end for 13: return S

(n L/K d + d n L/K -d)n 2 K )
for Algorithm 13. This gives us the following condition for a trade-off :

(5.6)

d n L/K + dn L/K n 2 K -dn 2 L -d = n 3 K l(n 3 L/K (n L + 1) -(n K + 1)).
When n L/K = 2 for example, this becomes

d 2 -2dn 2 K -d = n 3 K l(15n K + 7
). Thus following the analysis for the naive versions of our algorithm we obtain that the relative version with early abort is advantageous compared to the absolute one for d up to

√ 2n 2 K (n K + 2 log 2 x 2 )(15n K + 7)
which is better than the naive trade-off by a factor of O(n K ).

Experimental results

We compare in these section the practical performances of the methods described previously with the generic algebraic methods implemented in Pari/Gp [START_REF]PARI/GP version 2.11.2[END_REF], which is the function nfroots. Our implementation is (mainly) in Gp, and is publicly available. 2Recall that we assume that

Z K (f ) ⊂ Z[B], with B = (b 1 , . . . , b n ) being some Q-basis of K.
Given x ∈ K we will keep denoting by x 1 , . . . , x n its coefficients relative to B. In almost all our experiments, we chose B to be Z[θ] with θ = X mod P K (X), where P K (X) is a fixed polynomial defining the field K.

Number fields are drawn randomly through the choice of their defining polynomial following a given distribution. When we consider general number fields, meaning not from a special family such as cyclotomic number fields, P K (X) will be drawn with random coefficients in a given interval of the form -2 s , 2 s with s ∈ N. This somewhat arbitrary choice has been used in the literature [START_REF] Belabas | Topics in computational algebraic number theory[END_REF] and allows us to study the average behaviour of our algorithms, for a well defined notion of "average". Finally, we consider two specific classes of number fields, namely cyclotomic fields in Section 6.3.3 and real Kummer fields in Section 6.3.4, because they showcase nicely the good and bad behaviours of our algorithms (especially our relative method) and Pari/Gp nfroots. Remark 6.1. We checked the number of roots retrieved by our algorithms, and all roots were retrieved by both methods (absolute and relative). 6.1. Instability of nfroots. We observed experimentally that over generic number fields, nfroots is not stable, and that fields could be divided into two groups. We call bad fields those number fields for which nfroots behave poorly, and good fields the rest of them. In order to obtain better observations, we split them by minimising the sum of their medians, that we denote by m 1 and m 2 respectively. To showcase this unstable behaviour we give some statistical data regarding the running time of nfroots, AbsoluteRoots and AbsoluteRoots in Table 2. In Table 2 one can see that there are about 10% of fields for which the running time of nfroots explodes. The corresponding median m 2 is up to 127 times larger than the median m 1 corresponding to the rest of the fields. Algorithm 6 and Algorithm 13 are more stable. For these algorithms m 2 never exceeds 2m 1 . The instability of nfroots has the following consequence. For a majority of number fields, nfroots clearly outperforms AbsoluteRoots (it is more than 10 times faster for [K : Q] = 100) and this difference is growing with the dimension. However, in average, the timings obtained for both algorithms are similar.

Potential explanation. The determining parameter seems to be the possibility of retrieving an inert prime. Following the search for good primes implemented in Pari/Gp, we evaluated the proportion of fields for which an inert prime will be found, see Table 3. Table 3. Proportion of fields for which no inert prime has been found

These proportions tend to follow the ones found previously, such has presented in Table 2. Additionnally we recorded the running times over the two kind of fields, as showcased in Table 3. The results presented in Tables 2 and3 are very similar, which confirms the fact that the determining parameter regarding the instability of nfroots is the use of inert primes. Remark 6.2. In the following, for nfroots, we will systematically present the average value of the execution times over all fields, over "good" fields and over "bad" fields, in order to have a more complete picture of its behaviour. We will write m 1 and m 2 the two last quantities. 6.2. Absolute method. We study the impact of the different parameters of the problems which are the size of the polynomial P K (X), the number of roots |Z K (f )|, and the size of the roots log 2 x 2 . We also differentiated between number fields K such that r 1 > 0 or such that r 1 = 0, since the matrices used to decode do not have exactly the same sizes. However, since the results are very similar we only present here the data for r 1 > 0. Data when σ(K) ⊂ C \ R can be found Appendix B.3. 6.2.1. Choice of P K (X). We study the impact of two parameters linked to P K (X), namely deg P K (X) which is the dimension of K, and the size of its coefficients. In our experiments, we fixed the parameters of the problem linked to f (T ) ∈ K[T ]. More precisely we considered f (T ) such that:

• deg f (T ) = 50; • f (T ) splits in K, i.e. |Z K (f )| = deg f (T ); • ∀x ∈ Z K (f ), log 2 x ∞ 10. Then we considered P K (X) = p 0 + p 1 X + • • • + p n-1 X n-1 + X n ∈ Z[X]
for increasing degrees n, and several coefficient sizes s(P K ) = log 2 P K ∞ . More precisely for sizes s(P K ) ∈ {1, 10}, we picked polynomials P K (X) such that ∀i ∈ 0, n -1 , p i ∈ -2 s(P K ) , 2 s(P K ) , and this for n increasing. The data obtained are shown in Figures 5 and18.

One can remark that the time efficiency of all three methods are widely influenced by the dimension [K : Q]. It is easily explained by the fact that all three methods require the computation of a LLL-reduced basis of a lattice with rank equal to [K : Q]. Moreover the volume of said lattice depends also on the 2, the difference between m 1 and m 2 widens when [K : Q] increases.

The parameter s(P K ), i.e. the coefficient size of the defining polynomial of K, also influences the performances of all three algorithms. Our heuristic method seems to be slightly less impacted by this parameter.

One can see from Figure 5 and Figure 18 that AbsoluteRoots is less efficient than nfroots, at least for the fixed shape of f (T ). The heuristic method AbsoluteRootsHeur -using heuristic norm evaluation and formula to compute the precision -is way more efficient than the certified version. It is also more efficient than nfroots on average, and compete with its best running times in a number of cases. Our method seems to be more influenced by the dimension of K than the algorithm of Pari/Gp, at least when the latter runs at its best. 6.2.2. Size of the roots. We now study how the size of the elements of Z K (f ) impacts the performance of the different algorithms. To this end we fixed the parameters linked to P K (X) and f (T ):

• deg f (T ) = 50; • f (T ) splits in K, i.e. |Z K (f )| = deg f (T ); • s(P K ) = 1; • deg P K (X) ∈ {25, 50}.
We did experiments for increasing size of roots. Let us denote by s Z this size, i.e. ∀x ∈ Z K (f ), log 2 |x i | ∈ 0, s Z . The results can be found in Figure 19.

One can see that our algorithm is more influenced by s Z than nfroot. This is certainly due to the fact that the lattices reduced for decoding during the algorithm described in [START_REF] Belabas | A relative van Hoeij algorithm over number fields[END_REF] are ideals, and more precisely prime powers ideals. These are usually easier to reduce, especially if one can use a pre-reduction such as mentioned by Belabas, or the documentation of Pari/Gp [START_REF]PARI/GP version 2.11.2[END_REF]. Remark that the difference of running time for nfroots between bad and good fields seems constant here.

Partial conclusion.

From the different situations explored and the data gathered, we can conclude that the certified version of our method AbsoluteRoots is in general less efficient than the algebraic method implemented in Pari/Gp. However, their running time are similar in average in some situations (see Regarding the impact of the different parameters, our method behaves less nicely with respect to the dimension and the size of the roots. This is certainly due to the nature of the lattices to be reduced in the two different methods. The algebraic method takes fully advantage of the nature of the lattice, which is a power of a prime ideal, thus mitigating the influence of the size of the vectors and the dimension. In the best cases, it uses a pre-reduction algorithm which hasten considerably the subsequent LLL reduction [START_REF] Belabas | A relative van Hoeij algorithm over number fields[END_REF].

Relative extensions.

Let us now consider relative extensions L/K, and study the efficiency of Algorithm 13. First we look into the impact of our heuristic strategies. Then we compare this method to Algorithm 11. Finally, we study both algorithms together with nfroots over cyclotomic fields and Kummer extensions.

Let us fix the notations. We will consider L/K together with

P K (X) ∈ Q[X] and P L (Y ) ∈ K[Y ] such that K ∼ = Q[X] (P K (X)) and L ∼ = K[Y ]
(P L (Y )) .

6.3.1. Impact of the heuristic strategies. We considered several versions of the relative method : the certified one as Algorithm 8, the heuristic one as Algorithm 13, and two intermediate versions, where either the precision or the search is heuristic. We studied the impact of (a) the degree of the equation f (T ), and (b) the size s Z of the roots. We considered extensions L/K such that [K : Q] = 30, [L : K] = 3, s(P K ), s(P L ) 1, and f (T ) splits in K. Additionnally, we fixed s Z = 10 when studying deg f (T ) and deg f (T ) = 25 when studying the other parameter. We focused on small parameters for these experiments, as we wished to illustrate the impact of the heuristic modifications that we described. The timings obtained can be found in Figure 7.

One can remark that both heuristic observations speed-up the computations, especially when the degree of f is increasing, as shown in Figure 7a. This leads to a speed-ub up to a factor 100 for the full heuristic implementation compared to the "naive" one. Moreover from both experiments, one can conclude that the impact of the heuristic search (using Algorithm 12) is more important than the one of the heurictic precision -at least for the small range of parameters considered.

6.3.2. Generic number fields. In this section, we study the performances of our most efficient procedures, i.e. the heuristic algorithms AbsoluteRootsHeur and RelativeRoots, over "generic" number fields. Here, the term "generic" refers to fields whose defining polynomials have coefficients uniformly drawn in segments of the form -2 s , 2 s . For practicability reasons, our experiments mainly deal with s = 1.

Number of roots.

We first study the influence of the number of roots, as it impacts the running time of RelativeRootsHeur. We considered extensions L/K such that [L : Q] = 90 and [L : K] ∈ {2, 3} with:

• s(P K ), s(P L ) 1;

• deg f (T ) = 50;

• ∀x ∈ Z K (f ), s(x) 10. The influence of the number of roots can be seen in Figure 8. The timings of the method AbsoluteRoots increase with the number of roots, while the ones for the relative algorithm RelativeRoots globally decrease, which is expected, see Appendix A. Indeed, with q f increasing, roots are retrieved earlier and the search space is updated more quickly. One can remark on these first comparisons, that Algorithm 13 can be between 5 and 30 times faster than Algorithm 11. Moreover, as expected, Algorithm 13 is slower when [L : K] is increasing. All these observations will be verified in other experiments.

Degree of the extension. Let us now consider the influence of the degree [L : K] of the extension considered. We already know that the running time of RelativeRoots depends exponentially on this parameter. We illustrate its impact on practical computations. As expected, the running time of Algorithm 13 is deeply impacted by an increase in the relative degree [L : K]. However, when compared to Algorithm 11, one can observe that this drawback is mitigated when considering increasing degrees [K : Q]. This shows that for a constant [L : K] using our relative method should asymptotically outperform the absolute methods AbsoluteRootsHeur.

Cyclotomic fields.

In this section we study the performances of AbsoluteRootsHeur, RelativeRoot-sHeur and nfroots over cyclotomic fields. We will write K m the cyclotomic field Q(ζ m ) with conductor m. We study these fields because they are widely used in applied mathematics such as cryptography¿ Moreover, since their generic defining polynomials have small norms, nfroots is particularly efficient.

Additionally our relative method always apply be used over these fields. Indeed, K m always has a totally real subfield K + m such that [K m : K + m ] = 2. Moreover, since K + m = K τ m where τ is the complex conjugation, the search space has deg f elements. We use this structure only in our first experiments. Results are gathered in Figure 10.

If we compare the timings obtained to previous data such as presented in Figure 5 or Figure 18, both AbsoluteRootsHeur and nfroots seem more efficient than over randomly generated number fields. It is particularly the case of the latter.

The Pari/Gp nfroots is more efficient than our absolute method AbsoluteRootsHeur over all fields. Our relative method seems to compete with the implementation of Pari/Gp [START_REF]PARI/GP version 2.11.2[END_REF] with the set of parameters fixed in the experiments over "bad" fields, see Figure 10b. It is again more influenced by the dimension than nfroots (in its best behaviour). Additionally since we know from Section 6.2 that the methods using complex embeddings have a worse behaviour with respect to the size of the roots, it seems that using only K + m is not enough to beat the implementation of Pari/Gp over cyclotomic fields. Note however that most of these fields do have other subfields, which can be themselves cyclotomic fields. For example, if m = p r with p a prime integer, then writing m = p r such that r < r we have that K m is a subfield of K m such that [K m : K m ] = p r-r . Using the extension K m /K m would lead to a search space with d p r-r elements. We ran some experiments over such extensions for p ∈ {2, 3}, data are gathered in Table 5. Again we chose s Z = 50 and deg f (T ) = 50 (resp. deg f (T ) = 55) for p = 2 (resp. p = 3). We retrieve similar timings and asymptotically, the choices p = 2, r = 2 and p = 3, r = 1 should outperform nfroots. Remark that as expected AbsoluteRoots is the least efficient algorithm.

) ∈ Q r such that [K : Q] = p r . Fix K = Q( p √ m 1 , . . . , p √ m r-1
). Then L/K is an extension over which one can take full advantage of RelativeRoots. Indeed K can be embedded in R, so that Hom K (L, C) has one real embedding and p -1 complex ones. This gives a search space with deg f (T ) (p-1)/2 elements. We will compare AbsoluteRoots, RelativeRoots and nfroots of Pari/Gp [START_REF]PARI/GP version 2.11.2[END_REF]. We study these fields because real Kummer extensions are all "bad" fields for the p-adic method. Recall that is mentioned by [START_REF] Belabas | A relative van Hoeij algorithm over number fields[END_REF] that ideal lattices are usually easy to reduce -especially when one can use a pre-reduction algorithm -which occurs when the inertial degree of said ideal is large. Moreover we saw in Section 6.1 that nfroots behaved badly when the search for an inert prime was unfruitful. It turns out that over real Kummer fields of the form Q( p √ m 1 , . . . , p √ m r ), the inertial degree cannot be larger than the exponent p (see for instance [START_REF] Lesavourey | A note on the discriminant and prime ramification of some real Kummer extensions[END_REF]).

The first situation that we will explore will be the same as before, i.e. f (T ) is split. It will show how computations can be accelerated in good situations, and the difference between good and bad fields for nfroots. Then we will study the special case where f (T ) has degree p. It is the direct generalisation of f (T ) = T p -α p with α ∈ L, which is the type of equation that are to be solved in several tasks involving One can observe that both Algorithm 11 and Algorithm 13 outperform nfroots. Our relative method is particularly efficient, and is up to 100 times faster. This contrasts with cyclotomic fields. Indeed, compare timings reported in Figure 10 and Figure 11a for which the degree of the relative extension is 2.

Small degree equations. As mentioned we consider here polynomials f (T ) with small degrees, namely deg f (T ) = p over real Kummer fields Q( p √ m 1 , . . . , p √ m r ) of exponent p. For such degrees, the search space of Algorithm 13 is small enough to take full advantage of this method. Indeed, since the complex embeddings in Hom K (L, C) are all conjugates (except one real embedding), the cardinality of the search space is p p+1 2 .

Remark 6.3 (nfroots). In this configuration, nfroots does not follow the method described before. Indeed, when 3 deg f (T ) < [L : Q], the implementation of Pari/Gp uses Trager's method [START_REF] Trager | Algebraic Factoring and Rational Function Integration[END_REF][START_REF] Belabas | A relative van Hoeij algorithm over number fields[END_REF] for factorising polynomials. We will therefore refer to it as Trager, to differentiate it from the p-adic method.

We considered Kummer fields of exponent p in {2, 3, 5, 11} and the different objects are drawn such that:

• each m i is a prime number smaller than 40;

• deg f (T ) = p and |Z K (f )| = 1.
The data gathered can be found in Figure 12. In most cases our relative method is way more efficient than the two others. It can go up to 500 times faster for p = 3 for example. The method Trager implemented in Pari/Gp is always worse than both our algorithms when the roots are small, but it is stable when the size is increasing and it outperforms Algorithm 11 for large roots and p ∈ {2, 3, 5}. Note however that a basis lattice L l can be reduced once and used to solve different equations. Thus, a batch strategy is possible with AbsoluteRootsHeur, which is not the case with Trager.

If one compares the data gathered in Figures 12a and12b for p = 2 and p = 5 respectively -for which the degrees [L : Q] and the size of the search space are similar -one can see that the timings for RelativeRootsHeur are around 10 times lower for p = 5. This is due to the fact that the dimension of the subfield K over which decodings are made is smaller in this case. These observations are confirmed with the timings gathered in Figure 12c.

Finally, one can remark in Figure 12d that the size of the search space is important, as the difference between RelativeRootsHeur and AbsoluteRootsHeur is less important for p = 11. However in this case as for the others, it seems that the size of the roots is less of a problem for the relative method than for AbsoluteRootsHeur.

6.3.5. Small dimensions, small degree and large roots. We consider a final situation to showcase the performances of the algorithms studied here, namely when f (T ) has large roots and deg f (T ) is small as well as [K : Q]. This situation is encountered in its extreme in the Number Field Sieve with deg f (T ) = 2 and [K : Q] usually smaller than 10. In our experiments, we considered deg f (T ) = 10 and [K : Q] ∈ {12, 30}. Data are gathered in Figure 13.

As already observed, Pari/Gp nfroots is asymtotically more efficient than the absolute method Ab-soluteRoots. However RelativeRoots offers again a certain advantage compared to nfroots, especially for larger dimensions, here [L : Q] = 30. Note that Magma function Roots becomes quickly the least efficent method by a large factor. the following formula:

P(X = k) = k+m-1 k N -m-k M -m N m .
We will write X ∼ N HG(N, M, m).

The negative hypergeometric distribution describes exactly what we want to study. Indeed, it arises as follows. Consider a set of N elements, containing M "success elements" and N -m "fail elements". Then if one draws uniformly in the set without replacement until m successes are found, then the number of failures drawn follows a negative hypergeometric distribution.

Proposition A. 3 ([20]). Let N, M, m be integers, and X be a random variable such that X ∼ N HG(N, M, m). Then one has:

E[X] = m N -M M + 1
and Var[X] = m (N -M )(N + 1) (M + 1)(M + 2) 1 -m M + 1 .

We are essentially interested in the average cost, so we focus on the expectation. Then, assuming the search is naïve, the average number of "failed" decodings done in Algorithm 8 before finding one root is d n +1 s+1 . The average number of "failed" decodings before finding all the roots is s d n +1 s+1 .

Proof. Let X 1 be the random variable representing the number of failures before finding the first root, and X s be the random variable of the number of failures before finding all the roots. Clearly one has X 1 ∼ N GH(d n , s, 1) and X s ∼ N GH(d n , s, 1), and can apply directly the formula of the expectation from Proposition A.3 to find E[X 1 ] and E[X s ].

The study is slightly more complex when using UpdateTree. One can remark that the number of elements removed from the search space Z by UpdateTree depends on the index of the state. We will therefore consider the random variables corresponding to the number of failures between two found solutions.

Notation A.5. Let L/K be an extension of number fields such that [L : K] = n. Consider f (X) ∈ L[X] such that |Z K (f )| = s. We will denote by x (1) < • • • < x (s) the elements of Z K (f ) ordered in Z. For each k ∈ 1, s we will consider several random variables.

(1) X (k) is the random variable corresponding to the number of failures between the (k -1)-th solution and the k-th solution. (2) X (k) 1 is the random variable corresponding to the number of failures in the first coordinate between the (k -1)-th solution and the k-th solution.

(3) X (k) 2

is the random variable corresponding to the number of failures occurred between the (k -1)th solution and the k-th solution such that j 1 = x .

we obtain

E[X (j+1) 1 ] = d -s -E[X (i) 1 ] + (s -j + 2)E[X (j) 1 ] -(d -s) s -j + 1 = E[X (j) 1 ].
Then remark that X

(1)

1 ∼ N HG(d, s, 1), which gives the desired result.

Remark A.8. One can see that the gain of using UpdateTree increases with s. Indeed if f (X) has only one root, then the expected number of decodings is the same for both methods. However, if s = deg f (X) then the expected number of decodings with the naive search is d d(d n-1 -1)

d+1

, whereas it is

d-1 i=0 (d-i) n-1 -1 2
using UpdateTree.

Let us analyse more precisely the difference between the two procedures.

Notation A.9. Let L/K be an extension of number fields such that [L : K] = n. Consider f (X) ∈ L[X] such that |Z K (f )| = s. For each k ∈ 1, s we will consider several random variables, all related to a naïve search.

(1) X (k) naive is the random variable corresponding to the number of failures between the (k -1)-th solution and the k-th solution.

(2) Y (k) naive is the random variable corresponding to the number of failures which occured before the k-th solution is found. Note that we did similar experiments using an integral basis of O K instead of the equation basis (1, X, . . . , X n-1 ) and obtained similar results, which can be found in Figure 17. We were to smaller degrees because of the cost of computing such basis. One can see that ratio of q t by 1 + ln n ln ln(n)/(s ln 2 + ln(n)/2) is larger than 1 only for very small dimensions, which also happens for the equation basis. In practice, the additional precision that is required does not impact significatively the running times the algorithms. B.3. Absolute method. In this section we give data corresponding to experiments presented in Section 6.2, in the case where r 1 = 0, and consequently σ(K) ⊂ C \ R.

  λ 1 , . . . , λ n ) which gives a lattice of R n+1 represented by the row matrix

  n i=1 λ i α i = S. Then one can consider the similar matrix

Definition 2 . 7 (

 27 GSO). Given a basis B, we will call the basis B outputted by Algorithm 1 the GSO of B.

Theorem 2 . 17 .

 217 Consider L a lattice of rank r, B = (b 1 , . . . , b r ) a δ-LLL reduced basis of L for δ = 3/4, and B the GSO of B. Then the following properties are true.

(

bi 2 b i Make t more orthogonal to b i 4 : end for 5 :

 45 return v -t

Notation 3 . 5 .

 35 If σ(K) ⊂ R, we denote by σ(B) l the first column vector of a basis matrix B(B, σ, l). If σ(K) ⊂ R, we write σ(B) l = [ (σ(B) l ) , (σ(B) l )] for the matrix composed of the two first column vectors of B(B, σ, l).

Lemma 3 . 10 .

 310 Consider K a number field, L l = L(B, σ, l) a basis matrix of K, and x ∈ Z[B]. For any integral vector λ ∈ B(0, 2 n m x /C) we get the following lower bound for λB l 2

Proposition 3 . 20 .

 320 Consider a number field K, B a Q-basis of K and f (T ) ∈ K[T ] such that Z K (f ) ⊂ Z[B]. Then for input (K, B, f (T )),the algebraic complexity of lattice operations of Algorithm 6 (reduction of a basis lattice L l , GSO computation and decoding) are respectively in O(n 4 l +n 3 l 2 ), O(n 3 ) and O(dn 2 ), where n is the dimension [K : Q].

4. 1 .

 1 Decoding in a subfield. First let us describe how one can reduce knowledge of embeddings related to the extension L/K to decodings in K. Fix Ω an algebraic closure of L/K. We will use the relative Minkowski embedding σ L/K : x ∈ L → (σ(x)) σ∈Hom K (L,Ω) . It defines a K-linear embedding of L ∼ = K n into Ω n where n is the degree of L/K. More precisely, let us fix E = (e 1 , . . . , e n ) a K-basis of L and let x = x 1 e 1 + • • • + x r e n ∈ L. We assume that the action of each σ ∈ Hom

Figure 2 .Figure 3 .

 23 Figure 2. Ratios of running times of SpecLLL to LLL plotted against the precsion l, for σ(K) ⊂ R and several dimensions n

( 3 ) 2 σ - 1 K 2 2

 3212 the value B f = B f,T2 B satisfies the desired property. This bound can be quite large compared to M (f ) := sup{ x | x ∈ Z K (f )}. Without extrainformation this is the best one can do. However, one can use heuristic evaluations for x 2 2 , giving smaller results than B f . Consider σ ∈ Hom(K, C) and x ∈ K. Then one has |σ(x)| 2 = n i=1

  (a) s(PK ) = 1 (b) s(PK ) = 5

Figure 4 . 1 : w ← t 2 :

 412 Figure 4. Logarithms of maximum ratios of M (f ) by HeuristicNorm(f ) plotted against n = [K; Q] for several s, and s(P K ) ∈ {1, 5}

Dimension

10 Figure 5 .

 105 Figure 5. Average timings (s) of nfroots, AbsoluteRoots and AbsoluteRootsHeur plotted against deg P K (X) for randomly generated P K (X) such that r 1 > 0, with s(P K ) ∈ {1, 10}

Figure 6 .

 6 Figure 6. Average timings (s) of nfroots, AbsoluteRoots and AbsoluteRootsHeur plotted against s Z for randomly generated P K (X) such that [K : Q] = 25 and [K : Q] = 50, with r 1 > 0

  (a) deg f varying (b) sZ varying

Figure 7 .

 7 Figure 7. Timings (s) of certified and heuristic versions of RelativeRoots plotted against deg f (T ) (resp. s Z ) for randomly generated P K (X), P L (Y )

3 Figure 8 .

 38 Figure 8. Average timings (s) of AbsoluteRoots and RelativeRoots plotted against q f for randomly generated P K (X), P L (X) and f (T ), such that [L : Q] = 90 and deg f (T ) = 50.

  (a) [K : Q] = 15 (b) [K : Q] = 25

Figure 9 .

 9 Figure 9. Average timings (s) of AbsoluteRoots and RelativeRoots plotted against [L : K] for randomly generated P K (X), P L (Y ) and f (T ), such that [K : Q] ∈ {15, 25} and deg f (T ) = 50.

Figure 10 .

 10 Figure 10. Average timings (s) of AbsoluteRootsHeur, RelativeRoots and nfroots plotted against [K m : Q] for cyclotomic fields of conductor m such that 10 m 500 and [K m : Q] < 150, for s Z = 50.

  RelativeRoots, [L : K] = 3 3.9 7.1 33.1 (S-)units or class group[START_REF] Biasse | Improved techniques for computing the ideal class group and a system of fundamental units in number fields[END_REF][START_REF] Fieker | On Reconstruction of Algebraic Numbers[END_REF][START_REF] Pohst | Algorithmic Algebraic Number Theory[END_REF]. In particular, this task arose in several practical works these past few years[START_REF] Bauch | Short Generators Without Quantum Computers: The Case of Multiquadratics[END_REF][START_REF] Lesavourey | Short Principal Ideal Problem in multicubic fields[END_REF][START_REF] Biasse | Fast multiquadratic S-unit computation and application to the calculation of class groups[END_REF][START_REF] Bernard | Log-S-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP[END_REF][START_REF] Biasse | Norm relations and computational problems in number fields[END_REF]. Split equation. We considered split polynomials f (T ) of degree 50 for increasing size of roots s Z , over Kummer fields of the form L = Q( p √ m 1 , . . . , p √ m r ) with p ∈ {2, 5}. Moreover [L : Q] = 128 if p = 2, [L : Q] = 125 if p = 5, and each m i is a prime number smaller than 40. The results are shown in Figure 11.

Figure 11 .

 11 Figure 11. Average timings (s) of AbsoluteRootsHeur, RelativeRoots and nfroots plotted against s Z for Kummer fields of exponent p ∈ {2, 5}.

Figure 12 .

 12 Figure 12. Average timings (s) of AbsoluteRoots and RelativeRoots and Trager plotted against s Z for randomly generated Kummer fields L/K with exponent p ∈ {2, 3, 5, 11} and deg f (T ) = p.

Proposition A. 4 .

 4 Let L/K be an extension of number fields such that[L : K] = n. Consider f (X) ∈ L[X] such that |Z K (f )| = s and write d = deg f (X).

Lemma A. 6 .

 6 Y(k) is the random variable corresponding to the number of failures which occured before the k-th solution is found. Let L/K be an extension of number fields such that[L : K] = n. Consider f (X) ∈ L[X] such that |Z K (f )| = s.Then one has the following:∀k ∈ 1, s , Y (k) = k j=1 X (j) 1 (d -j + 1) n-1 + X (j) 2

Finally(d n- 1 -

 1 we will denote by S (k)X the difference X (k)naive -X(k) and byS (k) Y the difference Y (k) naive -Y (k) .Proposition A.10. Let L/K be an extension of number fields such that[L : K] = n. Consider f (X) ∈ L[X] such that |Z K (f )| = s. Write d = deg f (X). Then, for k ∈ 1, s we have E[X naive ] E[Y (k)] and the following is true: (d -i) n-1 ).Proof. First, for all k ∈ 1, s we will denote by c k the integer d -k + 1. Then, from the proofs of Lemma A.6 and Proposition A.7 we get E[X(k) . Now let us determine how this difference evolves with k. Clearly c k decreases when k increases, therefore so doesE[X (k) ]. Since E[X (k) naive ] is constant, we can conclude that S (k) X increases with k. Let us express S (k) Y . Given any sequence (u n ) n let us denote u n+1 -u n by ∆(u, n). Remark that S ∆(S X , i). Moreover one has ∆(S X , i) = E[X (i+1) ] -E[X (i) ] = (2d -s + 1)(-c n-1 i+1 + c n-1 i ) 2(s + 1)

Figure 15 .

 15 Figure 15. Timings (s) for σ(K) ⊂ R plotted against the precision

5 Figure 16 .

 516 Figure 16. Maximum ratios of q t by 1 + ln n ln ln(n)/(s ln 2 + ln(n)/2) plotted against n = [K : Q], for several s.

Figure 17 .

 17 Figure 17. Maximum ratios of q t by 1 + ln n ln ln(n)/(s ln 2 + ln(n)/2) plotted against n = [K : Q] for several s, where B is an integral basis of O K

  (a) s(PK ) = 1 (b) s(PK ) = 10

Figure 18 .Figure 19 .

 1819 Figure 18. Average timings (s) of nfroots, AbsoluteRoots and AbsoluteRootsHeur plotted against deg P K (X) for randomly generated P K (X) such that r 1 = 0, with s(P K ) ∈ {1, 10}

end if 9: end while 10: return B Theorem 2.18 (Complexity

  of LLL[START_REF] Nguyen | An LLL Algorithm with Quadratic Complexity[END_REF]). Consider L = L(B) ⊆ R n a lattice of rank r, and M = max{log 2 b 2 | b ∈ B}. Then for input B, one can compute a LLL-reduced basis of L in time complexity

	7:	else Swap(b i , b i-1 ) and i ← max{2, i -1}
	8:
	(2.3)	O r 2 n(r + M )M M(r) .
	Remark 2.19. When considering a full-rank lattice, i.e. r = n, we get an algebraic complexity O(n 4 M +
	n 3 M 2 ).
	Babaï's nearest plane algorithm. In order to solve BDD instances, one can use an algorithm due to [1],
	and called the nearest plane algorithm. It is an inductive technique, described in Algorithm 4, which is
	essentially a process of size-reduction (Alg. 2)
	Algorithm 4 Babaï's Nearest Plane Algorithm -NearestPlane
	Require: t ∈ R n , B = (b 1 , . . . , b r ) a basis of a lattice L, B the GSO of B
	Ensure: v ∈ L a close vector of t
	1: v ← t
	2: for i = r down to 1 do
	3:

  Now let us express some broad trade-off between our absolute and relative methods, considering only computations linked to lattice reduction and decoding. We forget about the GSO computation since it is done only once and is negligeable with respect to the lattice reduction. Consider L/K a number field extension and write n L , n K and n L/K for the degrees [L : Q], [K : Q] and [L: K]

	respectively. Following Propositions 3.20 and 4.5 we can conclude that the complexity of Algorithm 6
	due to lattice reduction and decoding is O(n 4 L l + n 3 L l + dn 2 L ) while these operations amount to O(n 4 K

4.3. Trade-off.

Table 1 .

 1 Number of steps before early aborts, for random targets in random number fields with s(P K ) = 10.

	4: Z ← FloatPolynomialRoots(f σ , l)
	5: S ← ∅
	6: for z ∈ Z do
	7:	y, b ← TestDecodeHeur(L l , z)						Early abort nearest plane
	8:	if b and f (y) = 0 then						Verification through finite fields
	9:	S ← S ∪ {y}
	10:	end if
	11: end for
	12: return S
		Dimension		25 50 75 100 125
			min	1	1	1	1	1
		s Z = 1	max	6	7	5	6	6
			average 2.7 2.4 2.5 2.2 2.8
			min	1	2	1	1	1
		s Z = 50	max	4	7	5	4	6
			average 2.5 2.8 2.7 2.3 2.8

Table 2 .

 2 Statistical data regarding the running time of nfroots, AbsoluteRoots and AbsoluteRoots over random number fields such that s(P K ) = 5.

		(a) nfroots
	Dimension [K : Q] 25	50		75	100
	# bad fields (%)	49	13		10	12
	m 1 (s)	2.37 20.41	55.51	125.92
	m 2 (s)	3.10 174.00 2189.93 16081.07
	average (s)	2.76 40.08	269.67 1989.31
	(b) AbsoluteRoots
	Dimension [K : Q] 25	50	75	100
	# bad fields (%)	65	77	68	67
	m 1 (s)	1.59 39.53 318.24 1637.11
	m 2 (s)	2.69 66.44 539.42 2646.72
	average (s)	2.31 60.44 467.41 2285.76
	(c) AbsoluteRootsHeur
	Dimension [K : Q] 25	50	75	100
	# bad fields (%)	57	71	72	61
	m 1 (s)	0.42 3.86 15.95 54.84
	m 2 (s)	0.61 5.31 21.72 67.19
	average (s)	0.53 4.88 19.98 62.33

Table 4 .

 4 Running time of nfroots, AbsoluteRoots and AbsoluteRoots over random number fields for which inert primes can be found or not.

	(a) nfroots
	Dimension [K : Q] 25	50	75
	Good fields (s)	3.1 17.8	55.5
	Bad fields (s)	4.9 164.1 2177.9
	(b) AbsoluteRoots
	Dimension [K : Q] 25	50	75
	Good fields (s)	2.3 52.5 437.1
	Bad fields (s)	2.3 52.2 403.1
	(c) AbsoluteRootsHeur
	Dimension [K : Q] 25 50	75
	Good fields (s)	0.5 4.7 21.7
	Bad fields (s)	0.5 4.7 20.7

  6.3.4. Kummer extensions. Let us now focus on real Kummer extensions, meaning such that L =

	Q(

p √ m 1 , . . . , p √ m r )

, where p 2 is a prime integer and (m 1 , . . . , m r

Table 5 .

 5 Running time of nfroots, AbsoluteRoots and AbsoluteRoots over cyclotomic fields of conductor m = p r with p a prime integer.

Code publicly available at https://github.com/AndLesav/nf_polynomial_roots

https://github.com/AndLesav/nf_polynomial_roots

Andrea Lesavourey is funded by the Direction Générale de l'Armement (Pôle de Recherche CYBER), with the support of Région Bretagne.

Appendix A. Average cost of the search

Let us study the average cost of the search phase of Algorithm 8 or Algorithm 13. In particular we will determine the average number of decodings that will occur before finding all roots. If one denotes by σ 1 , . . . , σ n the elements of Hom K (L, C), then the two algorithms can be described as a search without replacement in the set Z = Z 1 × • • • × Z n where Z i = Z σi .

Remark A.1. A cartesian product S = S 1 × • • • × S n will be ordered using the lexicographic order. This means that for all (x, y)

From now on, let us consider the sets Z i as ordered sets of elements z i,j with z i,j < z i,j ⇐⇒ j < j . Moreover we consider that we run through Z following the lexicographic order. Assume that the state of the computation is at the state with index j = (j 1 , . . . , j n ) ∈ 1, deg f (X) n , and that we found a root x. We can write x = (z 1,j1 , . . . , z n,jn ). Then the action of UpdateTree on Z is as follows. We mentioned that it removes z i,ji from Z for all i ∈ 1, n . This amounts to removing z i,ji from Z for all i ∈ 2, n and updating the index by doing j 1 ← j 1 + 1 and for all i > 1, j i ← 1.

Definition A.2. Let N, M, m be integers satisfying m M N . A random variable X taking nonnegative values follows a negative hypergeometric distribution with parameters (N, M, m) if it satisfies

after the (k -1)-th root and before the k-th root are found. Recall that after each new solution is found, UpdateTree removes one element of each Z i , i > 1. Therefore, one obtains

Because the search is done following the lexicographic order, it is easy to see that for each fixed

failures. the number of j 1 that are passed such that

Proposition A.7. Let L/K be an extension of number fields such that

Then, for k ∈ 1, s , the average number of "failed" decodings done in Algorithm 8 before finding k roots is

Proof. Using Lemma A.6 and by linearity of the expectation, one has:

is the number of failures found during the search through the set {x

We know there is exactly one solution in this set. Therefore we have . The search is done over the set Z 1 minus the elements visited before x (j-1) 1 included. It is a set with cardinal number

Now let us determine X

which contains s -(j -1) success elements. Therefore we have E[X a, s -(j -1), 1), for all possible a. Using the law of total expectation E[X] = E[E[X|Y ]] between two variables X and Y , it is easy to see that we have

It is possible to use this recurrence relation to obtain an expression of E[X

1 ] in closed-form. As a matter of fact, we will prove that E[X

, and since

which leads to

).

Finally we can write

Appendix B. Extra data B.1. Different versions of LLL. In this section we present the timings obtained when comparing the efficiency of LLL with our method SpecLLL (Alg. 9), which correspond to the ratio presented in Figures 2 and3. One can find said timings in Figures 14 and15. As mentioned previously, Fplll is faster than Magma or Pari/Gp. One can remark that the latter is around 5 times slower than Fplll asymptotically. This gives an idea of the timings that could be obtained for all our experiments by switching from the implementation of Pari/Gp to Fplll.