Paper 2022/980

Fast norm computation in smooth-degree Abelian number fields

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 Θ(nlogn)-bit norm of an element of weight n1/2+o(1) in a degree-n field; this method then uses n(logn)3+o(1) bit operations. An n(logn)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 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 times faster, and finish norm computations inside -unit searches times faster.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. ANTS 2022
Contact author(s)
authorcontact-abeliannorms @ box cr yp to
History
2022-08-03: approved
2022-07-31: received
See all versions
Short URL
https://ia.cr/2022/980
License
Creative Commons Attribution
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},
      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.