Fast norm computation in smooth-degree Abelian number fields

ePrint Report: Fast norm computation in smooth-degree Abelian number fields

Daniel J. Bernstein

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 …

computation eprint report fast