Paper 2022/980
Fast norm computation in smoothdegree Abelian number fields
Abstract
This paper presents a fast method to compute algebraic norms of integral elements of smoothdegree cyclotomic fields, and, more generally, smoothdegree Galois number fields with commutative Galois groups. The typical scenario arising in $S$unit searches (for, e.g., classgroup computation) is computing a $\Theta(n\log n)$bit norm of an element of weight $n^{1/2+o(1)}$ in a degree$n$ field; this method then uses $n(\log n)^{3+o(1)}$ bit operations. An $n(\log n)^{O(1)}$ operation count was already known in two easier special cases: norms from powerof2 cyclotomic fields via towers of powerof2 cyclotomic subfields, and norms from multiquadratic fields via towers of multiquadratic subfields. This paper handles more general Abelian fields by identifying towercompatible integral bases supporting fast multiplication; in particular, there is a synergy between towercompatible Gaussperiod integral bases and a fastmultiplication idea from Rader. As a baseline, this paper also analyzes various standard normcomputation techniques that apply to arbitrary number fields, concluding that all of these techniques use at least $n^2(\log n)^{2+o(1)}$ bit operations in the same scenario, even with fast subroutines for continued fractions and for complex FFTs. Compared to this baseline, algorithms dedicated to smoothdegree Abelian fields find each norm $n/(\log n)^{1+o(1)}$ times faster, and finish norm computations inside $S$unit searches $n^2/(\log n)^{1+o(1)}$ times faster.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Published elsewhere. ANTS 2022
 Contact author(s)
 authorcontactabeliannorms @ box cr yp to
 History
 20220803: approved
 20220731: received
 See all versions
 Short URL
 https://ia.cr/2022/980
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/980, author = {Daniel J. Bernstein}, title = {Fast norm computation in smoothdegree Abelian number fields}, howpublished = {Cryptology ePrint Archive, Paper 2022/980}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/980}}, url = {https://eprint.iacr.org/2022/980} }