Welcome to the resource topic for 2022/980
Title:
Fast norm computation in smooth-degree Abelian number fields
Authors: Daniel J. Bernstein
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.
ePrint: https://eprint.iacr.org/2022/980
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .