logo IMB
Retour

Séminaire de Théorie Algorithmique des Nombres

Calcul de racines de polynômes dans un corps de nombres

Andrea Lesavourey

( Irisa )

-

le 07 février 2023 à 10:00

Computing roots of elements is an important step when solving various tasks in computational number theory. It arises for example during the final step of the General Number Field Sieve~(Lenstra et al. 1993). This problem also intervenes during saturation processes while computing the class group or SS-units of a number field (Biasse and Fieker). It is known from the seminal paper introducing the LLL algorithm that one can recover elements of a given number field KK given approximations of one of their complex embeddings. This can be used to compute roots of polynomials. In the first part of this presentation, I will describe an extension of this approach that take advantage of a potential subfield kk, which replace the decoding of one element of KK by the decoding [K:k][K:k] elements of kk, to the cost of search in a set of cardinality d[K:k]d^{[K:k]} where dd is the degree of the targetted polynomial equation. We will also describe heuristic observations that are useful to speed-up computations. In the second part of the presentation, we will describe methods to compute ee-th roots specifically. When KK and ee are such that there are infinitely many prime integers pp such that mathfrakpp,pf(pp)quiv1(mode)\forall mathfrak{p} \mid p, p^{f(\mathfrak{p}\mid p)} \not equiv1 \pmod e, we reconstruct xx from x(modp1),dots,x(modpr)x \pmod {p_1}, dots, x \pmod {p_r} using a generalisation of Thomé's work on square-roots in the context of the NFS~(Thomé). When this good condition on KK and nn is not satisfied, one can adapt Couveignes' approach for square roots (Couveignes) to relative extensions of number fields K/kK/k provided [K:k][K:k] is coprime to ee and infinitely many prime integers pp are such that each prime ideal p\mathfrak{p} of Ok\mathcal{O}_k above pp is inert in KK.