-
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
-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
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
, which replace the decoding of one element of
by the decoding
elements of
, to the cost of search in a set of cardinality
where
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
-th roots specifically. When
and
are such that there are infinitely many prime integers
such that
, we reconstruct
from
using a generalisation of Thomé's work on square-roots in the context of the NFS~(Thomé). When this good condition on
and
is not satisfied, one can adapt Couveignes' approach for square roots (Couveignes) to relative extensions of number fields
provided
is coprime to
and infinitely many prime integers
are such that each prime ideal
of
above
is inert in
.