The norm map is one of the basic tools in algebraic number theory, the study of number fields. The norm map takes each numberfield element α to a rational number. This rational number is the determinant of multiplication by α; equivalently, the resultant of the field polynomial and the α polynomial.
Computing norms of many small elements of the ring of integers of a number field is one of the central bottlenecks in traditional classgroup computations, traditional unitgroup computations, and filteredSunit attacks against IdealSVP. Normcomputation software is readily available in packages such as PARI and NTL, building on many years of algorithmic research.
The point of this page is that some special number fields support much faster attacks against exactly the same problem, computing norms of many small ring elements. Full details are available in

a 2022 paper "Fast norm computation in smoothdegree Abelian number fields";

an
abelianfields
software package (described in Appendix A of the paper), testing that the main algorithms described in the paper work as specified; and 
a
cyclo2power
software package (described in Appendix B of the paper), focusing on the case of powerof2 cyclotomics and illustrating how to streamline the algorithms.
The speeds demonstrated by cyclo2power
are, at sizes of cryptographic interest,
more than 100000 times faster
than what has been achieved for most number fields.
The paper shows that similar speedups are possible
for any smoothdegree cyclotomic field.
This work builds on many preexisting components. For example, computing norms via subfields is textbook material; asymptotic analyses have already appeared in the literature for two special cases, powerof2 cyclotomics and multiquadratics; and the paper's generalization to smoothdegree Abelian fields builds on a long line of previous work, going back to Gauss's introduction of what are now called Gauss periods. See the paper for credits and references.
More broadly, there is already a long history in algebraic number theory of problems that have been intensively studied for general number fields and shown to have particularly efficient solutions for some special number fields, especially the extreme case of cyclotomic fields. See Section 2.6 of the 2021 paper "Risks of lattice KEMs" for examples and references.
What makes a number field special
There are two main parts to the speedup described above. The first part simply applies automorphisms of the number field to share norm computations across many inputs. This contributes a speedup factor close to the number of automorphisms. (See Section 5.4 of the 2022 paper for reasons that the speedup is not exactly the number of automorphisms.)
Generically, a number field has just one automorphism, the identity map; this by itself does not provide any speedup. Having extra automorphisms is a special feature of a number field.
Fortunately for the first speedup, people often choose degreen number fields having n automorphisms. These are called "Galois" number fields, and produce a first speedup factor close to n. For example, cyclotomic fields are Galois. (There are also various intermediate cases: number fields that have extra automorphisms without being Galois.)
The second part of the speedup exploits transitivity of norms through a tower of subfields. This is the central topic of the 2022 paper.
Generically, a number field has no subfields other than itself and the field of rational numbers. Having extra subfields is another special feature of a number field.
Fortunately for the second speedup, people often choose number fields with extra subfields. These choices are typically smoothdegree "Abelian" number fields.
Abelian number fields are a special case of Galois number fields, namely those for which the automorphism group is commutative. A smoothdegree Abelian number field has a tower of subfields where each degree is just (log n)^o(1) times the previous degree. For example, a powerof2 cyclotomic field is an Abelian field and has a tower where each degree is just 2 times the previous degree.
By the Kronecker–Weber theorem, a number field is Abelian if and only if it is a subfield of a cyclotomic field. The 2022 paper exploits cyclotomic structure for fast operations at every level of the tower of subfields, and obtains a speedup factor n^(1−o(1)) in each individual norm computation. This combines with the first speedup factor to produce an overall speedup factor n^(2−o(1)).
A degree that is somewhat smooth already provides most of the exponent improvement: for example, a tower with degrees 1,n^(1/3),n^(2/3),n provides an overall speedup factor around n^(5/3). It would be interesting to extend the techniques to further Galois number fields.
The easy way to fully enable both speedups is to take a smoothdegree cyclotomic field, such as a powerof2 cyclotomic field. To instead stay as far away as possible from these speedups, take any number field of prime degree n having Galois closure of degree factorial(n). Almost all number fields of prime degree n have Galois closure of degree factorial(n), and there are various reasonably efficient techniques to ensure that one has not bumped into Abelian fields and other exceptional cases.
The paper
[abeliannorms] (PDF) Daniel J. Bernstein. "Fast norm computation in smoothdegree Abelian number fields." 59pp. Algorithmic Number Theory Symposium (ANTS) 2022, to appear. Document ID: 6c338bc06ca0c734f22cb48bacc4b65ea666cd81. Date: 2022.07.31. 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 Sunit 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 degreen 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 Sunit searches n^2/(log n)^{1+o(1)} times faster.
The abelianfields
software
The abelianfields
software
carries out various tests that the main algorithms
in the
paper
work as specified.
The abelianfields
software
is written in a highlevel language,
Sage,
to help readers check the match between the software
and the paper.
Readers interested in reducing overhead per ring operation
should instead see the
cyclo2power
software.
To download, unpack, and run
the latest version of abelianfields
:
cd
wget m https://sunit.attacks.cr.yp.to/abelianfieldslatestversion.txt
version=$(cat sunit.attacks.cr.yp.to/abelianfieldslatestversion.txt)
wget m https://sunit.attacks.cr.yp.to/abelianfields$version.tar.gz
tar xzf sunit.attacks.cr.yp.to/abelianfields$version.tar.gz
cd abelianfields$version
make
Archive: 20220711
The cyclo2power
software
The cyclo2power
software
is a C library computing norms
of integral elements of powerof2 cyclotomic fields.
For simplicity,
the library uses GMP for multiplications;
even with that constraint,
the library is typically between 100 and 1000 times
faster than NTL for each norm computation
for sizes of cryptographic interest.
This is on top of the first speedup factor,
almost n for a degreen powerof2 cyclotomic field.
To download, unpack, compile, and run measurements
for the latest version of cyclo2power
:
cd
wget m https://sunit.attacks.cr.yp.to/cyclo2powerlatestversion.txt
version=$(cat sunit.attacks.cr.yp.to/cyclo2powerlatestversion.txt)
wget m https://sunit.attacks.cr.yp.to/cyclo2power$version.tar.gz
tar xzf sunit.attacks.cr.yp.to/cyclo2power$version.tar.gz
cd cyclo2power$version
make
./example
./dettest
Archive: 20220530
Version: This is version 2022.07.31 of the "Norms" web page.