The norm map is one of the basic tools in algebraic number theory, the study of number fields. The norm map takes each number-field 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 class-group computations, traditional unit-group computations, and filtered-S-unit attacks against Ideal-SVP. Norm-computation 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 smooth-degree 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 power-of-2 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 smooth-degree 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, power-of-2 cyclotomics and multiquadratics; and the paper's generalization to smooth-degree 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 degree-n 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 smooth-degree "Abelian" number fields.

Abelian number fields are a special case of Galois number fields, namely those for which the automorphism group is commutative. A smooth-degree Abelian number field has a tower of subfields where each degree is just (log n)^o(1) times the previous degree. For example, a power-of-2 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 smooth-degree cyclotomic field, such as a power-of-2 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 smooth-degree 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 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.

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 high-level 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://s-unit.attacks.cr.yp.to/abelianfields-latest-version.txt
    version=$(cat s-unit.attacks.cr.yp.to/abelianfields-latest-version.txt)
    wget -m https://s-unit.attacks.cr.yp.to/abelianfields-$version.tar.gz
    tar -xzf s-unit.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 power-of-2 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 degree-n power-of-2 cyclotomic field.

To download, unpack, compile, and run measurements for the latest version of cyclo2power:

    cd
    wget -m https://s-unit.attacks.cr.yp.to/cyclo2power-latest-version.txt
    version=$(cat s-unit.attacks.cr.yp.to/cyclo2power-latest-version.txt)
    wget -m https://s-unit.attacks.cr.yp.to/cyclo2power-$version.tar.gz
    tar -xzf s-unit.attacks.cr.yp.to/cyclo2power-$version.tar.gz
    cd cyclo2power-$version
    make
    ./example
    ./det-test

Archive: 20220530

---

Version: This is version 2022.07.31 of the "Norms" web page.