Ideal Norm Computation

The norm of an ideal is the number of residue classes modulo it. It is the primary size measure for ideals, it is multiplicative, and it is cheap to compute from the standard representation.

Definition and computation

Properties

Multiplicative

The norm of a product is the product of the norms. The single most useful property, and the basis of every consistency check on ideal arithmetic.

Agrees with element norm

For a principal ideal, the ideal norm is the absolute value of the element norm.

Prime ideals

A prime above a rational prime p has norm a power of p, the exponent being the residue degree.

Finiteness

Only finitely many ideals have norm below any bound, which is what makes factor bases finite.

The degree relation

Norms as a size measure

Reduction algorithms seek ideals of small norm in a given class, and factor bases consist of prime ideals of norm below a bound. In both cases the norm is the quantity being minimised or bounded — see factor base selection.

Smoothness

An ideal is smooth with respect to a factor base when its norm factors over the corresponding rational primes and each prime ideal appearing is in the base. Testing smoothness therefore begins with an integer factorisation of the norm — see smoothness.

Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 4.7.2. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.