### Fast norm computation in smooth-degree Abelian number fields

##### Abstract

This paper presents a fast method to compute algebraic norms of integral elements of smooth-degree cyclotomic fields, and, more generally, smooth-degree Galois number fields with commutative Galois groups. The typical scenario arising in $S$-unit searches (for, e.g., class-group 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 power-of-2 cyclotomic fields via towers of power-of-2 cyclotomic subfields, and norms from multiquadratic fields via towers of multiquadratic subfields. This paper handles more general Abelian fields by identifying tower-compatible integral bases supporting fast multiplication; in particular, there is a synergy between tower-compatible Gauss-period integral bases and a fast-multiplication idea from Rader. As a baseline, this paper also analyzes various standard norm-computation 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 smooth-degree 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.

Available format(s)
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. ANTS 2022
Contact author(s)
authorcontact-abeliannorms @ box cr yp to
History
2022-08-03: approved
See all versions
Short URL
https://ia.cr/2022/980

CC BY

BibTeX

@misc{cryptoeprint:2022/980,
author = {Daniel J. Bernstein},
title = {Fast norm computation in smooth-degree 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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.