Computing e-th roots in number fields

MaRDI QIDQ6438205zbMATH OpenFDO

Authors Olivier Bernard, Pierre-Alain Fouque, Andrea Lesavourey

Publication date 27 May 2023

Has companion code repository https://github.com/ob3rnard/eth-roots

Mathematics Subject Classification ID

Cyclotomic extensions (11R18) Class numbers, class groups, discriminants (11R29) Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40)

Abstract: We describe several algorithms for computing $e$-th roots of elements in a number field $K$, where $e$ is an odd prime-power integer. In particular we generalize Couveignes' and Thom'e's algorithms originally designed to compute square-roots in the Number Field Sieve algorithm for integer factorization. Our algorithms cover most cases of $e$ and $K$ and allow to obtain reasonable timings even for large degree number fields and large exponents $e$. The complexity of our algorithms is better than general root finding algorithms and our implementation compared well in performance to these algorithms implemented in well-known computer algebra softwares. One important application of our algorithms is to compute the saturation phase in the Twisted-PHS algorithm for computing the Ideal-SVP problem over cyclotomic fields in post-quantum cryptography.

This page was built for publication: Computing $e$-th roots in number fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438205)