tags: study notes class groups number theory

Notes from a First Encounter with Class Groups

Introduction

These notes grew out of an effort to understand the basics of class groups. With another VDF day around the corner, now seemed as good a time as any to get to grips with this material. Furthermore, class groups and lattices are part of the standard tool set in areas of cryptography relevant to blockchain and zero knowledge applications.

The central object of these notes are rings of integers

${\mathcal{O}}_K$ in number fields

$K$. These are objects borrowed from the realm of algebraic number theory (ANT). Topics derived from their study that have found application in cryptography include:

• Class Groups (of Imaginary Quadratic Number Fields),
• Lattices (ideal lattices or derived from groups of units of rings of integers),

and to a lesser extent (it seems),

• Orders (in Imaginary Quadratic Number Fields associated with elliptic curves).

Discussing the abstract theory of rings of integers is a necessary (?) prerequesite to properly introducing class groups; orders and lattices will be mentioned along the way.

Definitions will be given in due time. In the meantime, …

How is algebraic number theory relevant to cryptography?

Let's stick to the three topics introduced above.

In cryptographic applications, class groups are seen as a source of groups of unknown order (GUO). Recall that the order of a finite group

$G$ is its cardinality as a set. GUOs have been considered in the construction of candidate Verifiable Delay Functions (VDF) and Cryptographic Accumulators. They can also serve for as target groups for (polynomial) commitment schemes.

RSA groups

$(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$^[1] provide an alternative family of GUOs^[2]. However, generating RSA moduli

$N=pq$ requires either a trusted party^[3] or a non-trivial multiparty computation. Generating class groups^[4]

$\mathcal{Cl}(d)$ on the other hand "only" requires generating large negative square free public integers

$d$. Taking

$d=-p$ for a large prime

$p$ is a viable option.

For crypto applications the workflow for generating class groups^[5] is summed up below:

Understanding what comes out at the other end is challenging! A lot is known about these groups, but what matters most to GUO-type applications is that:

• these are always finite abelian groups (finiteness is a difficult theorem)
• and computing their order (i.e. size) is hard.

Note. For potential applications to VDFs, see Wesolovski's paper and Boneh, Bünz and Fish's survey. Applications of GUOs and class groups in particular to cryptographic accumulators are discussed in Bonej, Bünz and Fish's paper on the subject. DARK, a transparent polynomial comitment scheme, uses GUOs.

Lattice based cryptography aims to take advantage of computationally difficult problems related to lattices^[6]. A potentially important feature of this kind of cryptography is its conjectural resistance to quantum computers. It turns out that number fields are a breeding ground for nontrivial lattices^[7]. They crop up naturally in two distinct ways:

• as ideals of rings of integers
  ${\mathcal{O}}_K$,
• as the Log-unit lattice
  ${\mathrm{Log}}_K({\mathcal{O}}_K^{\times })$.

Orders^[8] and rings of integers also make a double-take-worthy appearance in isogeny-based cryptography, a subdomain of elliptic curve cryptography. When

$E/{\mathbb{F}}_q$ is an ordinary elliptic curve over a finite field

${\mathbb{F}}_q$, its ring of endomorphisms

$\mathcal{O}=\mathrm{End}(E)$ is an order in an imaginary quadratic number field

$K=\mathbb{Q}(\sqrt{D})$ associated to the (isogney class of the) curve

$E$. The class group

$\mathcal{Cl}(\mathcal{O})$ of invertible ideals of

$\mathrm{End}(E)$ acts on the isogeny graph of curves defined over

${\mathbb{F}}_q$ isogenous to

$E$ (isogeny graph). One can thus traverse this graph using ideals for transportation. These are considered to be hard homogeneous spaces, and can house Diffie-Hellman-type key exchanges.

Purpose of these notes

These notes contain a somewhat informal exposition of some basic topics in algebraic number theory as well as pointers as to how these are relevant to cryptography. The reader will find no proofs here, only assertions and my attempts at motivating the theory. My goal is to swiftly take the reader from the definition of algebraic integers to that of class groups. In keeping with that philosophy, I have tried to keep all theorems, lemmas, propositions and definitions short and written in plain english whenever possible.

However, motivation is key, and I have tried to follow some guiding threads. The angle that made the most sense to me^[9] is that of prime-ness: what does it mean to be prime? and factorization: when/how can one extend the standard theory of prime factorization of integers to other number systems?

Note. I discovered rather late in the writing process (thanks to Thomas Piellard) that there already exists an excellent blog post by Michael Straka on Class Groups for Cryptographic Accumulators. While we inevitably tread some common ground, I hope there is room for another blogpost on the subject.

• Notes from a First Encounter with Class Groups
  • Introduction
    • How is algebraic number theory relevant to cryptography?
    • Purpose of these notes
  • Algebraic Numbers and Algebraic Integers
    • Complex Algebraic Numbers …
    • … Form a Field
    • Complex Algebraic Integers …
    • … Form a Ring
    • Beautiful Integers
  • Number Fields
    • Definition
    • "Concrete" examples
    • The right equations
    • Algebraic indistinguishability of roots
    • Disincarnate number fields
  • Rings of Integers
    • Definitions and basic properties
    • Computing Rings of Integers is pretty complicated
    • Quadratic number fields
    • (Pure) cubic extensions
    • Cyclotomic fields
  • Primes and factorization
    • Primes and factorization: extrapolating from the integer case
    • Primes vs. Irreducibles
    • Existence and Uniqueness of Factorizations
    • The Bad News: Unique Factorization can fail in Rings of Integers
  • The Fix …
    • … is to switch from Elements to Ideals
    • Ideals as generalized elements
    • Prime ideals
  • More elements, more primes, fewer problems
    • More elements and more primes …
    • … Fixes the FTA
    • The main ingredient and its corollaries
    • Revisiting an earlier counter example
  • Ideal Groups
    • The monoid of ideals in a ring of integers
    • The group of fractional ideals of a ring of integers
    • Ideal Class group of a ring of integers
  • The Dirichlet Unit Theorem
    • Statement of the DUT
    • Example: Quadratic number fields
  • Where to go from here ?
    • Proper references
    • General theory of Dedekind domains
    • Connection with quadratic forms
    • Isogeny based crypto
• Appendix
  • Glossary
  • Units and structure of unit groups - classical examples and some facts

Algebraic Numbers and Algebraic Integers

In this section we define (complex) algebraic integers. In the sequel we will restrict to those algebraic integers that reside in small subfields of

$\mathbb{C}$ or, more generally, in abstract number fields.

Complex Algebraic Numbers …

Complex algebraic numbers are those complex numbers that satisfy a polynomial equation with rational coefficients, i.e. a complex number

$z$ is algebraic if it satisfies

$P(z)=0$ for a (nonzero) polynomial

$P$ with rational coefficients. Examples include:

• rational numbers
  $q\in \mathbb{Q}$, take
  $P=X-q\in \mathbb{Q}[X]$;
• square roots of rationals "
  $\sqrt{q}$" with
  $q\in \mathbb{Q}$, take
  $P=X^2-q\in \mathbb{Q}[X]$;
• higher roots such as "
  $\sqrt[r]{a}$", take
  $P=X^r-a$);

and many, many more … In particular roots of unity

$\zeta =\exp (\frac{2ik\pi }{n})$, with

$P=X^n-1$, are algebraic numbers.

Note. Not all complex numbers are algebraic. Those that aren't are called transcendental.

… Form a Field

It is a fact that the sum, product and quotient of algebraic numbers is still algebraic.

Theorem. The set

$\bar{\mathbb{Q}}$ of all complex algebraic numbers forms a subfield of

$\mathbb{C}$.

Note. This is not a priori obvious. Take

$\alpha =\sqrt{5}+\frac{1}{2}\frac{1}{\sqrt{3}}$: individually

$\sqrt{5}$ and

$\frac{1}{\sqrt{3}}$ are algebraic (they are roots of

$X^2-5$ and

$X^2-\frac{1}{3}$ respectively). To see that their

$\mathbb{Q}$-linear combination

$\alpha$ is algebraic we need to come up with a (nonzero) rational polynomial

$P$ annihilating

$\alpha$. We see that

${\alpha }^2=\frac{61}{12}-\frac{\sqrt{15}}{3}$ so that

$\alpha$ is a root of

$$P=(X^2-\frac{61}{12}{)}^2-\frac{5}{3}=X^4-\frac{61}{6}{X}^2+\frac{3481}{144}$$ Since

$\alpha$ is a root of this rational polynomial, we see that

$\alpha$ is algebraic. Doing similar manipulations by hand for more complicated expressions quickly becomes complicated.

Note. Chasing denominators in a rational polynomial

$P$ killing a particular algebraic number, we may assume the polynomials

$P$ to have integer coefficients. For instance, returning to

$\alpha =\sqrt{5}+\frac{1}{2}\frac{1}{\sqrt{3}}$, we see that it is also a root of

$144X^4-1464X^2+3481\in \mathbb{Z}[X]$

Complex Algebraic Integers …

We noted that, chasing denominators if necessary, complex algebraic numbers are the complex roots of integer coefficient polynomials. Algebraic integers are those algebraic numbers that are the roots of monic polynomials with integer coefficients.

All algebraic integers are algebraic numbers, but not all algebraic numbers are algebraic integers. The difference is already stark for rational numbers:

Lemma. A rational number is an algebraic integer iff it is an integer.

Thus "

$\sqrt{d}$" for

$d\in \mathbb{Z}$ is an algebraic integer, as a root of the monic integer polynomial

$X^2-d$, but

$\frac{2}{3}$ is not.

… Form a Ring

The example of rational algebraic integers shows that quotients of algebraic integers usually aren't algebraic integers (algebraic numbers, yes, but not algebraic integers in general). However, sums and products are:

Theorem. The set

${\mathcal{O}}_{\mathbb{C}}$ of all complex algebraic integers is a subring of

$\bar{\mathbb{Q}}$.

Again, this is not a priori obvious, see for instance Atiyah and MacDonald's Introduction to Commutative Algebra, chapter 5, for a general result. As a challenge, the reader may try to compute a monic, integer coefficient polynomial annihilating

$\sqrt[3]{2}+i$ from scratch. It's doable, but it's painful^[10] : )

Beautiful Integers

As an aside, a few years ago, pictures of certain collections of algebraic numbers / algebraic integers were published on the internet. John Baez in particular shared stunning pictures of such sets created by Dan Christensen and Sam Derbyshire. They have a presentation where one can read more about the intricate structure of the set of algebraic integers that are roots of polynomials with coefficients in

$\{-1,+1\}$ (and marvel at the beautiful pictures).

The pictures below, taken from wikipedia, represent certain subsets of algebraic numbers.

By Stephen J. Brooks (talk) (Stephen J. Brooks (talk)) CC BY 3.0, Link

Number Fields

Definition

Definition. A number field is a field^[11]

$K$ that is also a finite dimensional rational vector space:

${\dim }_{\mathbb{Q}}K<\mathrm{\infty }$.

In other words,

$K$ is a field^[11:1] and there exist elements

${\alpha }_1,\dots ,{\alpha }_d\in K$ such that any element

$x\in K$ can be expressed as

$$x=\sum _{k=1}^d{r}_k\cdot {\alpha }_k$$ for some rational numbers

$r_1,\dots ,r_d\in \mathbb{Q}$. Here

$d\ge {\dim }_{\mathbb{Q}}K$.

Elementary linear algebra shows that

Lemma. All elements of a number field

$K$ are algebraic.

"Concrete" examples

Examples are plentiful. For instance subfields of the complex numbers such as

$$\mathbb{Q}(\sqrt{2})=\{a+b\sqrt{2}\mid a,b\in \mathbb{Q}\}\text{or}\mathbb{Q}(i)=\{a+bi\mid a,b\in \mathbb{Q}\}$$ One easily verifies that these subsets of

$\mathbb{C}$ are subfields: they are stable under addition and product, contain the unit

$1$, and are stable under taking inverses.

Note. We called these examples "concrete" as they are realized as subfields of the complex numbers. It can be useful to consider "abstract" number fields, number fields obtained by formally adjoining roots of polynomial equations.

The right equations

When adjoining roots of polynomial equations

$P(X)=0$ one should restrict to irreducible polynomials, i.e. polynomials that can't substantially be factored over

$\mathbb{Q}[X]$. Consider for instance

$P=X^4-X^2-2$: this polynomial is reducible, as

$P=(X^2+1)(X^2-2)$. As a consequence it has two qualitatively very different pairs of solutions :

$\pm \sqrt{2}$ and

$\pm \sqrt{-1}$. Obviously, "adjoining

$\sqrt{2}$ to

$\mathbb{Q}$" produces

$K=\mathbb{Q}[\sqrt{2}]$ a field that is substantially different from

$L=\mathbb{Q}[i]$ obtained by "adjoining

$\sqrt{-1}$ to

$\mathbb{Q}$". To wit:

$2$ is a square in

$K$ but not in

$L$.

Algebraic indistinguishability of roots

The complex roots of a given irreducible rational polynomial

$P$ are absolutely indistinguishable from an algebraic point of view.

• You can't tell
  $\sqrt{2}$ and
  $-\sqrt{2}$ apart from one another (the roots of the irreducible rational polynomial
  $X^2-2$) by algebraic manipulations^[12] alone.
• Neither can you tell any of
  $-\sqrt[3]{5}$,
  $e^{\frac{i\pi }{3}}\sqrt[3]{5}$ and
  $e^{-\frac{i\pi }{3}}\sqrt[3]{5}$ apart from one another (the three roots of the irreducible rational polynomial
  $X^3+5$) by algebraic manipulations^[12:1].

In the first example one might object: "one is positive, while the other is negative; surely that can't be overlooked!" But in terms of doing algebra^[12:2] with these quantities, both

$\sqrt{2}$ and

$-\sqrt{2}$ behave exactly the same, like some "abstract quantity"

$\delta$ subject to the sole constraint that its square be two (i.e.

$\delta$ is a root of

$X^2-2$).

Similarly one might object "

$-\sqrt[3]{5}$ is a real number while

$e^{\frac{i\pi }{3}}\sqrt[3]{5}$ and

$e^{-\frac{i\pi }{3}}\sqrt[3]{5}$ are not; surely that can't be overlooked!" But from an algebraic point of view^[12:3], these three roots behave precisely the same, like a "formal variable"

$\alpha$ subject only to the constraint that its cube be

$-5$ (i.e.

$\alpha$ is a root of

$X^3+5$).

To illustrate this, consider the problem of expressing

$\frac{1}{\delta +3}$ as a rational-linear combination of

$1$ and

$\delta$ alternatively with

$\delta =\sqrt{2}$ and

$\delta =-\sqrt{2}$. The method is the same in both cases: one multiplies this fraction by the "conjugate quantity" both in the numerator and denominator:

$\delta =\sqrt{2}$	$\delta =-\sqrt{2}$
$\begin{array}{rcl}{\displaystyle \frac{1}{\delta +3}}& =& {\displaystyle \frac{1}{\sqrt{2}+3}}\\ & =& {\displaystyle \frac{-\sqrt{2}+3}{(-\sqrt{2}+3)(\sqrt{2}+3)}}\\ & =& {\displaystyle 3-\sqrt{2}}\\ & =& {\displaystyle 3-\delta }\end{array}$	$\begin{array}{rcl}{\displaystyle \frac{1}{\delta +3}}& =& {\displaystyle \frac{1}{-\sqrt{2}+3}}\\ & =& {\displaystyle \frac{\sqrt{2}+3}{(\sqrt{2}+3)(-\sqrt{2}+3)}}\\ & =& {\displaystyle 3+\sqrt{2}}\\ & =& {\displaystyle 3-\delta }\end{array}$

Disincarnate number fields

The examples of number fields we gave up until now were "concrete" in the sense that they were subfields of the field of complex numbers. We noted that their algebra could be done purely formally. If we take this observation seriously we are led to construct "disincarnate" number fields by "adjoining formal roots" of irreducible polynomials to the rational numbers.

Definition. Let

$P$ be an irreducible polynomial over

$\mathbb{Q}$. There is a number field

$K_P$ obtained by formally adjoining a root of

$P$ to

$\mathbb{Q}$.

One can construct

$K_P$ as the quotient ring

$\mathbb{Q}[X]/⟨P⟩$ of rational polynomials modulo

$P$. This produces a number field called the rupture field of

$P$. Indeed, if one defines

$x$ to be the class of

$X$ mod

$P$, then

$x$ is a root of

$P$ in

$K_P$ and

$(1,x,\dots ,x^{d-1})$ forms a

$\mathbb{Q}$-basis of

$K_P$ where

$d=\mathrm{deg}(P)$.

Note. In concrete terms this means that one defines

$K_P$ as the set of polynomials "mod

$P$", and does operations "mod

$P$". Thus

$A\times B$ is computed by computing the ordinary product

$A\times B$, doing long division by

$P$ and returning the residue.

Note. "Abstract" or "disincarnate" number fields are conceptually useful: they dissociate the algebra of roots (of irreducible polynomials) from their happenstance realization as particular roots/subfields of

$\mathbb{C}$. In particular this point of view makes the following trivial:

Theorem. There are precisely

$n$ field homomorphisms

$\sigma :K_P\hookrightarrow \mathbb{C}$.

Indeed, to define such a

$\sigma$, it is enough to choose one of

$P$'s

$d$ distinct roots

$z_1,\dots ,z_d\in \mathbb{C}$ and to set

$\sigma (x):=z_k$, where

$x=X\mathrm{mod}P$. This uniquely pins down

$\sigma$.

One can iterate this construction by adjoining a formal root of any

$K_P$-irreducible polynomial

$Q\in K_P[X]$, and so forth. Remarkably, a single extension is enough to produce all number fields:

Primitive Element Theorem. Every number field is isomorphic to a number field of the form

$K_P$ for some irreducible rational polynomial

$P$.

Note. Distinct irreduible polynomials can produce identical^[13] number fields. For instance the fields

$K_P$,

$K_Q$ and

$K_R$, where

$P=X^2-3$,

$Q=X^2-12$ and

$R=X^2-4X+1$, are isomorphic. This is the reason why one usually insists on square free

$d$ when defining

$\mathbb{Q}(\sqrt{d})$: the square part of

$d$ is irrelevant.

Rings of Integers

In this section we introduce the main object of study of this note: the ring of integers

${\mathcal{O}}_K$ of a number field.

Definitions and basic properties

We stated earlier that all elements in a number field

$K$ are algebraic. Algebraic integers in

$K$ are far rarer. The ring of algebraic integers of a number field is the central object in these notes.

Definition. Let

$K$ be a number field. Its ring of integers

${\mathcal{O}}_K$ is the subring of all algebraic integers in

$K$.

If

$K$ is a concrete subfield of

$\mathbb{C}$, we have

${\mathcal{O}}_K={\mathcal{O}}_{\mathbb{C}}\cap K$. We can restate a previous lemma as

Lemma. The ring of rational integers

${\mathcal{O}}_{\mathbb{Q}}$ is the ring

$\mathbb{Z}$ of ordinary integers.

Note. The fact that the (so-called) ring of integers of

$\mathbb{Q}$ is the usual ring of integers

$\mathbb{Z}$ alone would be insufficient grounds to justify calling the other rings

${\mathcal{O}}_K$ "rings of integers". But the connection runs much deeper. As we will see, these "rings of integers"

${\mathcal{O}}_K$ satisfy a version of the fundamental theorem of arithmetic. This in turn allows one to define class groups.

While algebraic integers are rarer than algebraic numbers, it is simple to show that any

$\alpha \in K$ there will exist some positive (rational) integer

$c$ with

$c\cdot \alpha \in {\mathcal{O}}_K$. If follows that:

Lemma.

${\mathcal{O}}_K$ spans

$K$ as a rational vector space.

The additive structure of

${\mathcal{O}}_K$ can be made 100% precise:

Lemma. As an additive group,

${\mathcal{O}}_K\simeq {\mathbb{Z}}^n$ where

$n={\dim }_{\mathbb{Q}}(K)$.

One says that

${\mathcal{O}}_K$ is an order of

$K$ where

Definition. An order of

$K$ is any subgring

$R\subset K$ which spans

$K$ and whose additive group is isomorphic to

${\mathbb{Z}}^n$.

As with any new definition, one's first instinct should be to try to understand some simple examples. But…

Computing Rings of Integers is pretty complicated

Describing the integers of a number field turns out to be difficult business. The following are some classical families of number fields for which explicit descriptions of their rings of integers are available.

Quadratic number fields

Quadratic number fields are fields

$K$ with

${\dim }_{\mathbb{Q}}(K)=2$. If

$K$ is a quadratic number field, there exists a unique square free integer

$d\in \mathbb{Z}\setminus \{0,1\}$ such that

$K=\mathbb{Q}(\sqrt{d})=\{a+b\sqrt{d}\mid a,b\in \mathbb{Q}\}$^[14]. We say that

$K=\mathbb{Q}(\sqrt{d})$ is an imaginary quadratic number field when

$d<0$. The ring of integers of

$\mathbb{Q}(\sqrt{d})$ has a simple description depending on the residue of

$d$ mod

$4$:

• if
  $d\equiv 2,3\mathrm{mod}4$ then
  ${\mathcal{O}}_{\mathbb{Q}(\sqrt{d})}=\{\text{the set of all }a+b\sqrt{d}\text{ where }a,b\in \mathbb{Z}\}$
• if
  $d\equiv 1\mathrm{mod}4$ then
  ${\mathcal{O}}_{\mathbb{Q}(\sqrt{d})}=\{\text{the set of all }a+b\frac{1+\sqrt{d}}{2}\text{ where }a,b\in \mathbb{Z}\}$

Algebraic integers of a quadratic number field are called quadratic integers.

Note. This is worked out in section 7.2 of Baker's book.

Note.

$d\equiv 0\mathrm{mod}4$ is not on the list: if

$4=2^2$ divides

$d$, then

$d$ isn't square free.

Note. Keeping in line with the more formal point of view, one can cleanly define

$K$ as

$\mathbb{Q}[X]/⟨X^2-d⟩$ so that

$X$ mod

$X^2-d$ is a formal square root of

$d$ in

$K$.

Note. One often sets

$$\tau =\{\begin{array}{ll}{\displaystyle \sqrt{d}}& \text{if }d\equiv 2,3\mathrm{mod}4\\ {\displaystyle \frac{1+\sqrt{d}}{2}}& \text{if }d\equiv 1\mathrm{mod}4\end{array}$$ Then

${\mathcal{O}}_K=\mathbb{Z}[\tau ](/vgfFYxLiTPuj4OqmyDLIIw)=\{a+b\tau \mid a,b\in \mathbb{Z}\}$.

Note. Some values of

$d$ yield familiar numbers:

• $d=+5$: then
  $d\equiv 1\mathrm{mod}4$ and
  ${\mathcal{O}}_K=\mathbb{Z}[\varphi ]$ where
  $\varphi =\frac{1+\sqrt{5}}{2}$ is the golden ratio
• $d=-1$: then
  $d\equiv 3\mathrm{mod}4$ and
  ${\mathcal{O}}_K=\mathbb{Z}[i]$ are the Gaussian integers
• $d=-3$: then
  $d\equiv 1\mathrm{mod}4$ and
  ${\mathcal{O}}_K=\mathbb{Z}[j]$, where
  $j=\frac{1+i\sqrt{3}}{2}=\exp (2i\pi /3)$ is a primitive third root of unity, are the Eisenstein integers

(Pure) cubic extensions

The next simplest case after quadratic extensions are cubic extensions. This is where things start to get complicated, truly complicated. The general cubic extension

$K/\mathbb{Q}$ has the form

$\mathbb{Q}(\theta )$ where

$\theta$ is subject to a relation

${\theta }^3+p\theta +q$ with

$p,q\in \mathbb{Q}$ and

$-(27q^2+4p^3)\ne 0$. The latter condition ensures irreducibility of

$X^3+pX+q$. Explicit integral bases for

$K$'s ring of integers

${\mathcal{O}}_K$ exist but they are pretty complicated, see Voronoi's Method or the paper An Explicit Integral Basis for a Pure Cubic Field.

A simpler subcase is that of the pure cubic extensions

$K=\mathbb{Q}(\sqrt[3]{d})$ where

$d\ge 2$ is a cube free integer. A description of the ring of integers can be found in this math stackexchange answer. The "square free" case is treated as an exercise in a few books, see for instance Alan Baker's A Comprehensive Course in Number Theory example 10.1 page 107, exercise (ix) page 110 and exercise (vii) page 120.

Cyclotomic fields

The

$n$-th cyclotomic field

$\mathbb{Q}({\zeta }_n)$ is the subfield of

$\mathbb{C}$ generated by

$\mathbb{Q}$ and a primitive

$n$-th root of unity. Alternatively it is the splitting field of the

$n$-th cyclotomic polynomial. Its ring of integers is

$$\mathbb{Z}[{\zeta }_n]=\{\sum _{0\le k<\phi (n)}{a}_k{\zeta }_n^k|a_k\in \mathbb{Z}\}.$$ Here

$\phi (n)$ is Euler's totient function and the degree of the

$n$-th cyclotomic polynomial

${\mathrm{\Phi }}_n$, the minimal polynomial of

${\zeta }_n$. This isn't an easy result. Baker's account of the case where

$n=p$ is prime is good. In the comments to this MO answer, Keith Conrad sketches an argument for the case

$n=p^d$ is a prime power and how to derive the general case from there.

Primes and factorization

Number fields

$K$ and their rings of integers

${\mathcal{O}}_K$ provide a vast generalization of the rational numbers

$\mathbb{Q}$ and rational integers

$\mathbb{Z}$ (note that

${\mathcal{O}}_{\mathbb{Q}}=\mathbb{Z}$). Both have a satisfying theory of primes and unique factorization (uniquely representing things as products of prime powers). But, the extension is not completely straightforward.

Primes and factorization: extrapolating from the integer case

There are two equivalent but conceptually different ways to think of prime numbers in

$\mathbb{Z}$.

Primes as indivisible elements

Prime numbers are the positive integer

$p\in \mathbb{Z}$ that possess precisely two distint positive integer factors:

$1$ and themselves. Another way of saying the same thing is that

$p$ possesses no interesting factorization in

$\mathbb{Z}$: indeed, all its factorizations

$$p\times 1,1\times p,(-p)\times (-1)\text{and}(-1)\times (-p)$$ have one factor that is a unit^[15] of

$\mathbb{Z}$, i.e.

$\pm 1$.

We can use this as the template for a definition in an arbitrary ring

$R$ (in particular

${\mathcal{O}}_K$):

Definition. An nonzero and nonunit element

$\pi \in R$ is said to be irreducible if for any factorization

$\pi =a\times b$, either

$a$ or

$b$ is a unit in

$R$.

Thus the primes of

$\mathbb{Z}$ are the (positive) irreducible elements of the ring

$\mathbb{Z}$.

Primes as atoms of multiplication

Primes also play a basic role in factoring numbers. A (rational) prime is a positive integer

$p\in \mathbb{Z}$ such that whenever

$p$ divides a product

$a\times b$ of integers

$a,b$, it has to divide either

$a$ or

$b$ (and possibly both). Thus

$6$ isn't prime since

$6$ divides

$6=2\times 3$ yet

$6$ does not divide either

$2$ or

$3$.

We can similarly use this as the template for a definition in an arbitrary ring

$R$:

Definition. A nonzero and nonunit element

$p\in R$ is said to be prime if for any

$a,b\in R$ such that

$p$ divides

$a\times b$,

$p$ divides

$a$ or

$p$ divides

$b$ (or both).

Thus the primes of

$\mathbb{Z}$ are the (positive) prime elements of the ring

$\mathbb{Z}$.

The Fundamental Theorem of Arithmetic (FTA)

When working over the integers, irreducibles and primes coincide. They give rise to the same set of (positive) prime numbers

$\{2,3,5,7,11,\dots \}$ (if we restrict attention to the positive ones). Furthermore, we have the

FTA. Any positive integer

$n$ has a unique factorization as a product of primes.

This is the sort of theorem that we want to generalize to rings of integers

${\mathcal{O}}_K$. The main result is that the theorem generalizes but its generalization isn't straightforward. Note that this result contains two assertions: existence and uniqueness of a factorization.

Primes vs. Irreducibles

In a domain, all primes are irreducible. But in general there may be irreducibles that are not prime. In

$\mathbb{Z}$ (and more generally in any unique factorization domain) primes and irreducibles are of course the same: good old prime numbers (and their negatives).

Importantly, primes and irreducibles play very different conceptual roles. Irreducibles are useful for establishing existence results^[16] while primes are useful for uniqueness results^[17]. We quote two propositions from algebra to give an idea of what this means.

Theorem (Existence of Factorizations). Let

$R$ be a noetherian domain. Every nonzero nonunit of

$R$ can be expressed as a finite product of irreducibles.

Using slightly more symbols, for

$x\in R$ neither zero nor a unit, there is a positive integer

$n$ and irreducibles

${\pi }_1,\dots ,{\pi }_n$ such that

$x=\prod _{i=1}^n{\pi }_i$. The reader doesn't have to know what 'noetherian domains' are, it is enough to know that the rings of integers

${\mathcal{O}}_K$ fall in that category, so that this existence result applies to them. Thus, under some very mild conditions, existence of factorizations into products of irreducibles is a given.

Theorem (Uniqueness of Factorizations). Let

$R$ be a domain. Factorizations into product of primes, when they exist, are essentially unique.

To make that statement slightly more precise, if

$x\in R$ (nonzero and not a unit) has a factorization

$x=\prod _{i=1}^r{p}_i$ into a product of primes and if

$x=\prod _{i=1}^s{q}_i$ is yet another factorization of

$x$ into a product of primes, then

$r=s$ and (up to a permutation of the indices) there are units

$u_1,\dots ,u_r$ of

$R$ such that

$q_i=u_i{p}_i$ for all

$i=1,2,\dots ,r$.

Existence and Uniqueness of Factorizations

A domain

$R$ that satisfies the fundamental theorem of algebra is called a Unique Factorization Domain, UFD for short:

Definition. A Unique Factorization Domain is a domain

$R$ in which every nonzero nonunit element has an essentially unique^[18] factorization into a product of irreducibles.

We quote a result from algebra:

Proposition. Let

$R$ be a domain s.t. every nonzero nonunit element has a factorization as a product of irreducibles. Then

$R$ is a UFD iff all its irreducibles are prime.

This shows that a necessary condition for the FTA to hold in a ring

$R$ is that irreducibles and primes be the same. Proofs of these propositions can be found in this note.

The Bad News: Unique Factorization can fail in Rings of Integers

We claimed earlier^[19] that all

${\mathcal{O}}_K$ satisfy the 'Existence of Factorizations Theorem'. If our goal is to generalize the fundamental theorem of arithmetic to rings of integers, this is good news. All that is still needed in order to replicate the theory of primes and factorizations of

$\mathbb{Z}$ is uniqueness; half the battle is won!

But that hope is soon squashed: some rings of integers

${\mathcal{O}}_K$ contain irreducibles that fail to be prime. Examples are a dime a dozon. Consider

$K=\mathbb{Q}(\sqrt{-5})$, since

$-5\equiv 3\mathrm{mod}4$, we have

${\mathcal{O}}_K=\mathbb{Z}[\sqrt{-5}]=\{a+b\sqrt{-5}\mid a,b\in \mathbb{Z}\}$. The number

$6\in {\mathcal{O}}_K$ has two essentially distinct factorizations into irreducibles:

$$2\times 3=6=(1+\sqrt{-5})\times (1-\sqrt{-5})$$ One shows that

$2,3,(1+\sqrt{-5})$ and

$(1-\sqrt{-5})$ are irreducible^[20] but not prime as neither

$2$ nor

$3$ divide either

$(1+\sqrt{-5})$ or

$(1-\sqrt{-5})$ and vice versa.

The Fix …

Concrete examples show that the FTA does not extend verbatim to rings of integers in number fields. The non trivial step to restoring balance to the galaxy is to use ideals.

… is to switch from Elements to Ideals

We can restate prime-ness, divisibility, unique factorization etc… in a ring

$R$ in terms not of the elements of

$R$ but in terms of the ideals of

$R$.

Definition. An ideal

$I$ in a ring

$R$ is an additive subgroup

$I\subset R$ such that for all

$x\in I$ and

$r\in R$ the product

$rx$ is again in

$I$.

In other words, an ideal

$I$ is a (nonempty) subset of

$R$ such that if

$x,y\in I$ and

$r\in R$, then

$x\pm y\in I$ and

$rx\in I$. Ideals, particularly prime ideals, are at the heart of commutative algebra, the field that studies commutative rings and their modules. Ideals are plentiful:

Notation. Given

$x_1,\dots ,x_m\in R$, we define

$$⟨x_1,\dots ,x_m⟩=\{\sum _{k=1}^m{r}_k{x}_k|r_1,\dots ,r_m\in R\}$$

Sets of the form

$⟨x_1,\dots ,x_m⟩\subset R$ are called finitely generated ideals^[21]. In general rings there will be ideals that are not finitely generated, but in rings of integers

${\mathcal{O}}_K$, all ideals are finitely generated^[22]. Ideals of the form

$⟨x⟩$ (i.e. generated by a single element) are called principal ideals.

If

$I\subset {\mathcal{O}}_K$ is a nonzero ideal and

$\alpha \in I\setminus 0$, then

$\alpha \cdot {\mathcal{O}}_K=⟨\alpha ⟩\subset I$ shows that

$I$ is a full rank additive subgroup of

${\mathcal{O}}_K$. As such, general results about subroups of

${\mathbb{Z}}^n(\simeq {\mathcal{O}}_K)$ impose that

Lemma.

$(I,+)$ is isomorphic to

${\mathbb{Z}}^n$.

Note. The so-called trivial ideals are the zero ideal

$⟨0⟩=\{0\}$ and

$R$ itself:

$⟨1⟩=R$.

Note. There are varying nontational conventions for ideals…

• $I,J,K$ often represent ideals; there should never be a confusion with the field
  $K$
• $\mathfrak{a},\mathfrak{b},\mathfrak{c}$ do too
• The letters
  $\mathfrak{p},\mathfrak{q}$ are reserved for prime ideals (introduced later)

Ideals as generalized elements

Operations on Ideals

Let

$I,J,K$ be ideals in some ring

$R$. The following operations define new ideals of

$R$.

Sum of ideals. Define

$I+J=\{x+y\text{ where }x\in I,y\in J\}$.
Product of ideals. Define

$I\cdot J=\{\sum _i{x}_i{y}_i\text{ where }{x}_i\in I,y_i\in J\}$.
Divisibility. Define

$I$ divides

$J$, and write

$I\mid J$, if there is an ideal

$K$ with

$I\cdot K=J$.
Intersection of ideals. The intersection

$I\cap J$ remains an ideal.

There are other noteworthy operations but we don't need them here. Sums and products satisfy the expected commutativity, associativity and distributivity properties:

$$\{\begin{array}{lr}\text{Commutativity: }& I\cdot J=J\cdot I\text{and}I+J=J+I,\\ \text{Associativity: }& (I\cdot J)\cdot K=I\cdot (J\cdot K)\text{and}(I+J)+K=I+(J+K),\\ \text{Distributivity: }& (I+J)\cdot K=I\cdot K+J\cdot K\end{array}$$

Note. One has

$⟨x_1,\dots ,x_n⟩=\sum _{i=1}^n⟨x_i⟩$ and

$⟨x_i{⟩}_{1\le i\le n}\cdot ⟨y_j{⟩}_{1\le j\le m}=⟨x_i{y}_j{⟩}_{1\le i\le n,1\le j\le m}$.

Relating operations on elements to operations on ideals

In a ring

$R$ we can convert elements into (principal) ideals. Recall

$⟨x⟩=\{rx\mid r\in R\}$.

$$⟨\cdot ⟩:\{\begin{array}{ccc}R\setminus 0& ⟶& \left\{\begin{array}{c}\text{set of all nonzero prin-}\\ \text{cipal ideals of }R\end{array}\right\}\\ x& ⟼& ⟨x⟩\end{array}$$ When moving from elements to (principal) ideals, a little bit of information gets lost in the process. Indeed, different elements may give rise to the same (principal) ideal:

$⟨x⟩=⟨y⟩$ iff^[23]

$x$ and

$y$ are associates, i.e. there exists a unit

$u$ with

$y=ux$. But differing by a unit is pretty inconsequential for questions of divisibility and factorization, which is what we are interested in.

Some of the concepts that introduced for elements carry thus over to (principal) ideals in a ring

$R$^[23:1].

• $a,b\in R$ are associates iff
  $⟨a⟩=⟨b⟩$
• $u\in R$ is a unit iff
  $⟨u⟩=R$
• $a$ divides
  $b$ iff
  $⟨b⟩\subset ⟨a⟩$

Prime ideals

We slyly introduced one form of divisibility between (principal) ideals in the last bullet point: set theoretic containment. But having defined products of ideals, it would seem to make more sense to define divisibility between ideals in terms of the ideal product.

Two notions of divisibility for ideals

The most natural way to define divisibility for ideals is in terms of products:

$I\mid J$ when there exists an ideal

$K$ such that

$I\cdot K=J$. However, in most of commutative algebra, this relation does not play as prominent a rale as the weaker notion of (set theoretic) containment. Containment of ideals

$J\subset I$, can be seen as a weaker form of divisibility. Indeed,

Lemma. For arbitrary ideals

$I,J$ in a ring

$R$ one has

$I\mid J⟹J\subset I$

Let us introduce nonstandard notation

${\mid }^{\text{weak}}$ and

${\mid }^{\text{strong}}$ to mean respectively

• $I{\mid }^{\text{weak}}J⟺J\subset I$
• $I{\mid }^{\text{strong}}J⟺I\mid J⟺\mathrm{\exists }K,I\cdot K=J$.

Using this notation we can re-state the previous lemma:

Lemma.

$I{\mid }^{\text{strong}}J⟹I{\mid }^{\text{weak}}J$.

When restricted to principal ideals

$\mathfrak{a}=⟨a⟩$ and

$\mathfrak{b}=⟨b⟩$ the two notions coincide:

Lemma.

$\mathfrak{a}{\mid }^{\text{strong}}\mathfrak{b}⟺\mathfrak{b}{\mid }^{\text{weak}}\mathfrak{a}⟺a\mid b$.

In most rings, these two notions are very different

For non principal ideals (and arbitrary rings) the previous equivalence usually fails. Consider for instance the ring

$R=\mathbb{Z}[X]$ of polynomials with (rational) integer coefficients. Consider the three ideals

$I=⟨2,X⟩$,

$J=⟨2⟩$ and

$J^{\prime }=⟨X⟩$. One easily sees that

• $I$ is the ideal of all polynomials whose constant term is even,
• $J$ is the ideal of all polynomials with even coefficients,
• $J^{\prime }$ is the ideal of all polynomials whose constant term is
  $0$.

Then

$J,J^{\prime }\subset I$ i.e.

$I{\mid }^{\text{weak}}J,J^{\prime }$, yet no ideal

$K$ can satisfy either

$I\cdot K=J$ or

$I\cdot K=J^{\prime }$, i.e. neither

$I{\mid }^{\text{strong}}J$ nor

$I{\mid }^{\text{strong}}{J}^{\prime }$ hold.

Prime Ideals

The following is not the usual way to define prime ideals^[24], but in light of our emphasis on divisibility it is the most appropriate. Let

$R$ be a ring.

Definition. An ideal

$\mathfrak{p}$ is prime if for any ideals

$I,J$ of

$R$,

$I\cdot J\subset \mathfrak{p}⟹I\subset \mathfrak{p}$ or

$J\subset \mathfrak{p}$.

In other words,

$$\mathfrak{p}\text{ prime ideal of }R⟺(\text{for all ideals }I,J\text{,}\mathfrak{p}{\mid }^{\text{weak}}I\cdot J⟹\mathfrak{p}{\mid }^{\text{weak}}I\text{ or }\mathfrak{p}{\mid }^{\text{weak}}J)$$

This shows the connection with the notion of prime elements:

$$p\text{ prime element of }R⟺(\text{ for all }a,b\in R,p\mid a\cdot b⟹p\mid a\text{ or }p\mid b)$$

The connection is further strenghtened by

Lemma. Let

$p\in R$ be a nonzero nonunit:

$p$ is prime iff

$⟨p⟩$ is a prime ideal.

More elements, more primes, fewer problems

The insight of the generalization of the FTA is that by allowing "more elements and more primes" in the form of the non principal ideals and non principal prime ideals one can generalize the FTA to rings of integers

${\mathcal{O}}_K$^[25].

More elements and more primes …

To summarize, we can consider, in a domain

$R$,

• nonzero elements^[26] as special avatars of a larger class of "generalized elements": the (nonzero) principal ideals inside the larger set of all nonzero ideals,
• prime elements^[26:1] as special avatars of a larger class of generalized "primes": the (nonzero) principal prime ideals inside the larger set of all nonzero prime ideals,

And indeed, for most rings, this provides us with a much larger collection of objects that one may legitimately call "primes".

In the picture above, we identify the nonzero elements of

$R$ (up to association) with the set of all nonzero principal ideals. This identification is represented by the blue two headed arrows.

Note. In some rings, all ideals are principal. Domains with this property are called Principal Ideal Domains (PID for short).

… Fixes the FTA

We will first recast the Fundamental Theorem of Arithmetic (FTA) of the integers

$\mathbb{Z}$ in terms of ideals and their unique factorization into products of prime ideals. We then state (without proof) its extension to rings of integers

${\mathcal{O}}_K$ for arbitrary number fields

$K$.

Drawing Inspiration from the Integers

Recall the notation

$⟨a⟩=\{ak\mid k\in \mathbb{Z}\}$. The ring of (rational) integers is particular in the sense that all its ideals are principal^[27]. In other words, if

$I$ is an ideal of

$\mathbb{Z}$, there exists a unique nonnegative integer

$n$ with

$I=⟨n⟩$. As a consequence,

${\mid }^{\text{weak}}$ and

${\mid }^{\text{strong}}$ are the same.

$\mathbb{Z}$	With elements	With Ideals
Division	$a\mid b$	$\begin{array}{clc}⟨a⟩& {\mid }^{\text{weak}}& ⟨b⟩\\ ⟨a⟩& {\mid }^{\text{strong}}& ⟨b⟩\end{array}\}\text{ same thing}$
Associates	$b=u\cdot a$ for $u\in \mathcal{U}(\mathbb{Z})$	$⟨a⟩=⟨b⟩$
Product	$a\cdot c=b$	$⟨a⟩\cdot ⟨c⟩=⟨b⟩$
GCD	$d=gcd(a,b)$	$⟨d⟩=⟨a⟩+⟨b⟩$
LCM	$m=\mathrm{lcm}(a,b)$	$⟨m⟩=⟨a⟩\cap ⟨b⟩$
Primes	prime numbers $p$	nonzero prime ideals $⟨p⟩$
Set of Primes	$\{$ all positive primes $p$ $\}$	$\{$ all nonzero prime ideals $⟨p⟩$ $\}$
FTA	Every positive integer $n$ has a unique factorization into a product of primes $${\displaystyle n=\prod _{i=1}^r{p}_i^{m_i}}$$	Every nonzero ideal $I=⟨n⟩$ has a unique factorization into a product of prime ideals $${\displaystyle I=⟨n⟩=\prod _{i=1}^r⟨p_i{⟩}^{m_i}}$$

Note. GCD = greatest common divisor, LCM = lowest common multiple, FTA = Fundamental Theorem of Algebra.

The FTA for rings of integers

As promised, here (in the last box) is the version of the FTA for rings of integers

${\mathcal{O}}_K$ of number fields

$K$. We state it without proof, along the intermediary result that

${\mid }^{\text{weak}}$ and

${\mid }^{\text{strong}}$ are identical relations.

${\mathcal{O}}_K$	With elements	With Ideals
Division	$a\mid b$	$\begin{array}{clc}I& {\mid }^{\text{weak}}& J\\ I& {\mid }^{\text{strong}}& J\end{array}\}\text{ same thing}$
Associates	$b=u\cdot a$ for $u\in \mathcal{U}({\mathcal{O}}_K)$	$I=J$
Product	$a\cdot c=b$	$I\cdot J$
GCD	doesn't usually exist	$I+J$
LCM	doesn't usually exist	$I\cap J$
Primes	prime elements	nonzero prime ideals $\mathfrak{p}$
Set of Primes	$\{\text{primes }p\text{ up to association}\}$	$\begin{array}{c}\{\text{ principal prime ideals }⟨p⟩\}\\ \cap \\ \{\text{ all nonzero prime ideals }\mathfrak{p}\}\end{array}$
FTA	usually wrong	Every nonzero ideal $I$ has a unique factorization into a product of prime ideals $${\displaystyle I=\prod _{i=1}^r{\mathfrak{p}}_i^{m_i}}$$

The main ingredient and its corollaries

The theorem follows easily from an important proposition which we state here (without proof). The proof^[28], as well as how to derive the corollaries, can be found in Baker's book, Theorem 11.2. We provide further details in this separate note. Let

$I$ be any nonzero ideal in

${\mathcal{O}}_K$.

Theorem. There exists a nonzero ideal

$J$ such that

$I\cdot J$ is principal.

In other words, all (nonzero) ideals in

${\mathcal{O}}_K$ are invertible. With this result in hand, it is pleasantly easy to derive the following propositions. Let

$\mathfrak{a},\mathfrak{b},\mathfrak{c}$ be nonzero ideals in

${\mathcal{O}}_K$.

Cancellation.

$\mathfrak{a}\mathfrak{b}=\mathfrak{a}\mathfrak{c}⟹\mathfrak{b}=\mathfrak{c}$.
To contain is to divide^[29].

$\mathfrak{a}\mid \mathfrak{b}⟺\mathfrak{b}\subset \mathfrak{a}$ that is

$\mathfrak{a}{\mid }^{\text{strong}}\mathfrak{b}⟺\mathfrak{a}{\mid }^{\text{weak}}\mathfrak{b}$
Finite set of divisors. There are only finitely many ideals dividing a given ideal

$\mathfrak{a}$.
FTA. Every nonzero ideal is uniquely the product of finitely many prime ideals.

Revisiting an earlier counter example

We revisit the unfortunate situation

$2\times 3=6=(1-\sqrt{-5})(1+\sqrt{-5})$ mentioned earlier. The point of view described here is to factor the principal ideals

$⟨2⟩$ and

$⟨3⟩$. Using the fact that the ring of integers

${\mathcal{O}}_K=\mathbb{Z}[\sqrt{-5}]$ of

$K=\mathbb{Q}(\sqrt{-5})$ has an integral power basis

$(1,\tau )$, where

$\tau =\sqrt{-5}$, one may deduce from the factorizations

$X^2+5=(X+1{)}^2\mathrm{mod}[2]$ and

$X^2+5=(X+1)(X-1)\mathrm{mod}[3]$ of

$\tau$'s minimal polynomial

$X^2+5$ the factorizations

$$⟨2⟩=⟨2,1+\sqrt{-5}{⟩}^2\text{and}⟨3⟩=⟨3,1+\sqrt{-5}⟩\cdot ⟨3,1-\sqrt{-5}⟩$$ Furthermore, the ideals

$⟨2,1+\sqrt{-5}⟩$,

$⟨3,1+\sqrt{-5}⟩$ and

$⟨3,1-\sqrt{-5}⟩$ are prime (indeed, maximal) by inspection^[30]:

$${\mathcal{O}}_K/⟨2,1+\sqrt{-5}⟩\simeq {\mathbb{F}}_2\text{and}{\mathcal{O}}_K/⟨3,1\pm \sqrt{-5}⟩\simeq {\mathbb{F}}_3$$

We also get the prime factorizations of

$⟨1+\sqrt{-5}⟩$ and

$⟨1-\sqrt{-5}⟩$:

$$\begin{array}{rcl}⟨2,1+\sqrt{5}⟩\cdot ⟨3,1+\sqrt{5}⟩& =& ⟨6,2(1+\sqrt{-5}),3(1+\sqrt{-5}),(1+\sqrt{5}{)}^2⟩\\ & =& ⟨1+\sqrt{5}⟩\end{array}$$ and, given that

$⟨2,1+\sqrt{5}⟩=⟨2,1-\sqrt{5}⟩$,

$$\begin{array}{rcl}⟨2,1-\sqrt{5}⟩\cdot ⟨3,1-\sqrt{5}⟩& =& ⟨6,2(1-\sqrt{-5}),3(1-\sqrt{-5}),(1-\sqrt{5}{)}^2⟩\\ & =& ⟨1-\sqrt{5}⟩\end{array}$$

Ideal Groups

This section contains nothing new. We simply state consequences of the four preceding properties. In particular, we define the ideal class group of a number field

$K$. We state (without proof) the decidedly non trivial fact that this group is always finite.

The monoid of ideals in a ring of integers

In any domain

$R$, the set

$\mathcal{I}(R)$ of nonzero ideals along with ideal multiplication "

$\cdot$" forms a commutative monoid with unit

$⟨1⟩=R$. Recall that a (commutative) monoid is a set

$M$ with a multiplication "

$\cdot :M\times M\to M$" which is (commutative) associative and unital. The subset

$\mathcal{P}(R)$ of all (nonzero) principal ideals forms a submonoid.

Definition. A (nonzero) ideal

$I$ of

$R$ is said to be invertible if there exists

$J$ with

$I\cdot J$ principal.

The "main ingredient" from two sections ago states that all (nonzero) ideals in

${\mathcal{O}}_K$ for a number field

$K$ are invertible. Also, the results on existence and uniqueness of factorizations into prime ideals tells us that when

$R$ is the ring of integers

${\mathcal{O}}_K$ of a number field

$K$, its monoid of ideals

$\mathcal{I}({\mathcal{O}}_K)$ has special properties:

• every ideal
  $I\in \mathcal{I}({\mathcal{O}}_K)$ is "invertible mod
  $\mathcal{P}({\mathcal{O}}_K)$", in the sense that there exists
  $J\in \mathcal{I}({\mathcal{O}}_K)$ with
  $I\cdot J\in \mathcal{P}({\mathcal{O}}_K)$.
• $\mathcal{I}({\mathcal{O}}_K)$ is cancellative in the sense that
  $I\cdot J=I\cdot J^{\prime }⟹J=J^{\prime }$,
• furthermore, its structure is exceedingly simple:
  $$\begin{array}{rcl}(\mathcal{I}({\mathcal{O}}_K),\cdot )& \stackrel{\sim }{⟶}& {\displaystyle (\underset{\mathfrak{p}}{⨁}\mathbb{N},+)}\\ I& ⟼& ({\nu }_{\mathfrak{p}}(I){)}_{\mathfrak{p}}\end{array}$$

Where

${\nu }_{\mathfrak{p}}(I)$ denotes the multiplicity of

$\mathfrak{p}$ in

$I$: if

$I=\prod _{i=1}^r{\mathfrak{p}}_i^{m_i}$ is the decomposition of

$I$ into a product of prime ideals, then

$$\text{for all nonzero prime ideals }\mathfrak{p},{\nu }_{\mathfrak{p}}(I)=\{\begin{array}{ll}{m}_i& \text{ if }\mathfrak{p}={\mathfrak{p}}_i\\ 0& \text{ otherwise}\end{array}$$ In other words,

$\mathcal{I}({\mathcal{O}}_K)$ is the free monoid on the set of nonzero prime ideals.

Note. In the special case

$K=\mathbb{Q}$ and

${\mathcal{O}}_K=\mathbb{Z}$, the monoid of nonzero ideals is isomorphic to the monoid of positive integers

$\mathbb{N}\setminus 0$ under multiplication and the previous isomorphism is

$$(\mathbb{N}\setminus 0,\times )\simeq (\underset{p\text{ prime}}{⨁}\mathbb{N},+)$$

The group of fractional ideals of a ring of integers

We can convert these free abelian monoids into groups. The resulting group can be identified with the collection of so-called fractional ideals. The name is a little unfortunate, as these are actually (nonzero)

${\mathcal{O}}_K$-submodules

$M$ of the

${\mathcal{O}}_K$-module

$K$ with the property that for some

$x\in K$,

$xM\subset {\mathcal{O}}_K$.

Note. In the special case

$K=\mathbb{Q}$ and

${\mathcal{O}}_K=\mathbb{Z}$, fractional ideals are of the form

$q\mathbb{Z}\subset \mathbb{Q}$, for some positive rational number

$q$. The group of nonzero fractional ideals is thus isomorphic to the group of positive rationals

${\mathbb{Q}}_{+}^{\ast }$ under multiplication and the previous isomorphism is

$$({\mathbb{Q}}_{+}^{\ast },\times )\simeq (\underset{p\text{ prime}}{⨁}\mathbb{Z},+)$$

Ideal Class group of a ring of integers

We described how to associate to

${\mathcal{O}}_K$ the group of its "fractional ideals"

$\mathcal{FI}({\mathcal{O}}_K)$ and the subgroup of its "principal fractional ideals"

$\mathcal{FP}({\mathcal{O}}_K)$. This produces two short exact sequences

$$1\to \mathcal{U}(K)\to K^{\times }\stackrel{x\mapsto ⟨x⟩}{\to }\mathcal{FP}({\mathcal{O}}_K)\to 1$$ and

$$1\to \mathcal{FP}({\mathcal{O}}_K)\to \mathcal{FI}({\mathcal{O}}_K)\to \mathrm{Cl}({\mathcal{O}}_K)\to 1$$ where, by definition:

Definition.

${\mathcal{O}}_K$'s ideal class group

$\mathrm{Cl}({\mathcal{O}}_K)$ is the quotient group

$\mathcal{FI}({\mathcal{O}}_K)/\mathcal{FP}({\mathcal{O}}_K)$.

It is a simple fact that the ring of integers

${\mathcal{O}}_K$ of a number field

$K$^[31] is a PID iff it is a UFD. Also,

${\mathcal{O}}_K$ is a PID iff

$\mathcal{I}({\mathcal{O}}_K)=\mathcal{P}({\mathcal{O}}_K)$ iff

$\mathcal{FI}({\mathcal{O}}_K)=\mathcal{FP}({\mathcal{O}}_K)$ iff

$\mathrm{Cl}({\mathcal{O}}_K)=\{1\}$. Thus

Theorem. Are equivalent: (i)

${\mathcal{O}}_K$ is a PID (ii)

${\mathcal{O}}_K$ is a UFD (iii)

$\mathrm{Cl}({\mathcal{O}}_K)$ is trivial.

Non Examples. The rings

$\mathbb{Z}$ of rational integers,

$\mathbb{Z}[i]$ of Gaussian integers and

$\mathbb{Z}[j]$ of Eisenstein integers are PIDs^[32] and so their class groups are trivial.

The following is very much nontrivial:

Theorem. The ideal class group of a number field is finite.

Computing class groups is f*****g hard and involves topics we didn't discuss. It costs nothing, at this point, to remark that prime factorization implies that

$\mathrm{Cl}({\mathcal{O}}_K)$ is generated by the (nonzero) prime ideals

$\mathfrak{p}$. These are connected to good old (rational) primes by the theory of ramification of primes. Another ingredient in class group computations is Minkovski's bound, which helps narrow the search.

Example. The class group of

$\mathbb{Z}[\sqrt{-5}]$ is (isomorphic to)

$\mathbb{Z}/2\mathbb{Z}$ and generated by any one of the three ideals

$⟨2,1+\sqrt{-5}⟩$,

$⟨3,1+\sqrt{-5}⟩$ or

$⟨3,1-\sqrt{-5}⟩$ we encountered earlier.

The Dirichlet Unit Theorem

Statement of the DUT

We have collected some classical facts about, and computations of, unit groups of rings in an appendix. They represent what little I know (or knew at some point) about them. My impression is that for most rings

$R$ explicit descriptions of its units are rare, and explicit descriptions of the structure of unit groups

$\mathcal{U}(R)$ are even rarer.

It is then remarkable that for rings of integers

${\mathcal{O}}_K$ of number fields

$K$ both of these exist:

Lemma. An algebraic integer

$\alpha \in {\mathcal{O}}_K$ is a unit iff its norm

$N_{K/\mathbb{Q}}(\alpha )$ is

$\pm 1$.

In order for this note to be as non technical as possible we have omitted many of the standard tools of the theory. Chief among them: the norm

$N_{K/\mathbb{Q}}$ and trace

${\mathrm{Tr}}_{K/\mathbb{Q}}$ maps. Any book/set of lecture notes on ANT defines them.

For the following (non trivial) theorem to make sense we must define two integers

$s,t$ associated with the number field

$K$. Let

$n={\dim }_{\mathbb{Q}}(K)$ be

$K$'s dimension as a rational vector space. It follows from the Primitive Element Theorem quoted above^[33] that there are

$n$ distinct field embeddings

$\sigma :K\hookrightarrow \mathbb{C}$, say

${\sigma }_1,\dots ,{\sigma }_n$. Such an embedding is called real if it takes

$K$ to a subfield of the real numbers, and complex otherwise. If

$\sigma$ is complex, then composing it with complex conjugation yields a different embedding

$\bar{\sigma }$. Complex embeddings therefore come in pairs. We put

$s=$ number of real embeddings of

$K$,

$2t=$ number of complex embeddings of

$K$. Note that

$s+2t=n$.

Dirichlet's Unit Theorem. The unit group

$\mathcal{U}({\mathcal{O}}_K)$ is isomorphic to

${\mu }_K\times {\mathbb{Z}}^r$, where

${\mu }_K$ is the (finite cyclic) group of roots of unity of

$K$ and

$r=s+t-1(\ge 0)$.

The proof found in Baker (Theorem 12.3) is really worthwhile. I have collected some details about certain parts of that proof in a separate file.

Example: Quadratic number fields

The only situation that is easy enough for me to describe explicitely is that of quadratic number fields

$K=\mathbb{Q}(\sqrt{d})=\mathbb{Q}[X]/⟨X^2-d⟩$ for some squarefree integer

$d$. We use the notation

${\mathcal{O}}_K=\mathbb{Z}[\tau ]$ introduced in a previous section. There are two cases to distinguish:

• $d\le -1$: then
  $s=0$,
  $t=1$ and the two embeddings are defined by
  $\tau \mapsto \pm i\sqrt{|d|}$. Then
  $r=0$ and the unit group is a finite, cyclic group of roots of unity in
  $K$. For all
  $d<0$ except
  $d=-1$ and
  $d=-3$ the unit group is
  $\{-1,+1\}$; the nontrivial cases are
  • $d=-1$, then
    $\tau =i$ and
    $\mathcal{U}(\mathbb{Z}[i])=\{\pm 1,\pm i\}\simeq \mathbb{Z}/4\mathbb{Z}$,
  • $d=-3$, then
    $\tau =j=\exp (2i\pi /3)$ and
    $\mathcal{U}(\mathbb{Z}[j])=\{\pm 1,\pm j,\pm \bar{j}\}\simeq \mathbb{Z}/6\mathbb{Z}$.

• $d\ge 2$: In that case
  $s=2$,
  $t=0$, the two embeddings being defined by
  $X\mapsto \pm \sqrt{d}$. The roots of unity of
  $K$ are
  $\{\pm 1\}$. We have
  $r=1$ and there is a so-called fundamental unit
  $ϵ\in {\mathcal{O}}_K$ such that all units are of the form
  $\pm {ϵ}^m$, for
  $m\in \mathbb{Z}$.

This recovers the classical resolution of the so-called Pell equation, see in particular this section.

Where to go from here ?

Proper references

Readers who know the material will have noted some glaring omissions (beyond the total absence of proofs). For one, I barely mention norms^[34] at all. If you want a proper introduction to this material, you will find there is no shortage of excellent online course notes and books on these subjects. I can wholeheartedly recommend two such books: Paul Pollack's A Conversational Introduction to Algebraic Number Theory: Arithmetic Beyond Z, a gentle and very pleasant introduction to these matters, which spends a lot of time on the quadratic case, and Alan Baker's marvellous A Comprehensive Course in Number Theory, a model of exposition and economy. The latter, specifically chapters 10, 11 and 12, was my main reference in preparing these notes and learning the material. I have collected some notes regarding certain proofs found in that book in a separate document.

General theory of Dedekind domains

Class groups can be defined for a very broad collecion of rings, at least for so-called Dedekind domains, see wikipedia for basic definitions. These rings have the same remarkable "to contain is to divide" property for ideals that is the cornerstone of the present theory. The Fundamental Theorem of Arithmetic for Ideals carries over to these more general domains, and one can similarly define class groups. Finiteness, however, isn't guaranteed. The general theory is exposed in these (french) lecture notes by Jean-François Dat, and elsewhere in the litterature.

Connection with quadratic forms

The theory as presented here remains quite abstract. There are equivalent formulations that are amenable to concrete computer assisted computations.

The starting point is again a square free integer

$d$ and an associated quantity

$D$ called the "discriminant": if

$d\equiv 2,3\mathrm{mod}[4]$, set

$D=4d$, if

$d\equiv 1\mathrm{mod}[4]$, set

$D=d$. This time the object of interest are binary quadratic forms, that is: homogeneous degree two polynomial maps

$f:\mathbb{Z}\times \mathbb{Z}\to \mathbb{Z}$ of the form

$f(x,y)=a{x}^2+bxy+c{y}^2$^[35] with discriminant equal to

$D$, i.e. satisfying

$b^2-4ac=D$^[36]. We conflate

$f$ with the vector

$[a,b,c]$.

The prime example turns out to come from

${\mathcal{O}}_K$,

$K=\mathbb{Q}(\sqrt{d})$: the norm

$N_{K/\mathbb{Q}}$ restricted to the ring

${\mathcal{O}}_K$. Recall that its underlying additive group is isomorphic as a group to

${\mathbb{Z}}^2$, explicitely by choosing the

$\mathbb{Z}$-basis

$(1,\tau )$. One computes the norm in these coordinates:

$$N_{K/\mathbb{Q}}(x+y\tau )=(x+y\tau )(x+y\bar{\tau })=\{\begin{array}{ll}{x}^2-d{y}^2& \text{if }d\equiv 2,3[4]\\ x^2+xy+\frac{1-d}{4}{y}^2& \text{if }d\equiv 1[4]\end{array}$$ This defines a binary quadratic form and one easily checks its discriminant equals

$D$.

To tame the collection of all such forms (which is infinite), one considers them up to base change. That is we identify two such forms

$f,g$ if there exists a (direct) base change matrix

$U=\left(\begin{array}{cc}s& t\\ u& v\end{array}\right)$ (i.e.

$s,t,u,v\in \mathbb{Z}$,

$sv-tu=1$) such that

$f\circ U=g$. There are only finitely many equivalence classes of forms.

It turns out that (at least when

$d<0$) this finite set of equivalence classes is in one to one correspondence with the class group

$\mathcal{Cl}(d)$. Furthermore, this one to one correspondence is the shadow of a beautiful map that sends (nonzero) ideals

$I$ of

${\mathcal{O}}_K$ to the quadratic space

$(I,q_I)$, where

$q_I$ is simply the (suitably normalized) restriction of the norm form

$N_K/\mathbb{Q}$ to

$I$!

$$\begin{array}{ccc}\{\text{nonzero ideals of }{\mathcal{O}}_K\}& ⟶& \left\{\begin{array}{c}\text{quadratic forms on }{\mathbb{Z}}^2\\ \text{with discriminant }D\end{array}\right\}\\ I& ⟼& (I,q_I)\\ \downarrow \downarrow \downarrow & & \downarrow \downarrow \downarrow \\ \mathcal{Cl}(d)& \stackrel{\sim }{⟷}& \left\{\begin{array}{c}\text{equivalence classes of}\\ \text{binary quadratic forms}\end{array}\right\}\\ [I]& ⟷& [\text{iso. class of }(I,q_I)]\end{array}$$

(To be fair, the proper target of the first map is the category of oriented quadratic planes: free abelian groups of rank

$2$ with an orientation and a quadratic form of discriminant

$D$, and ideals on the left should be endowed with an orientation.)

An explicit construction can be found in the appendix to this paper. (The equivalence class of)

$({\mathcal{O}}_K,N_{K/\mathbb{Q}})$ corresponds to the neutral element

$[⟨1⟩]=[{\mathcal{O}}_K]$, and there are explicit algebraic formulas for computing the product of two representatives forms represented by

$[a,b,c]$ and

$[\alpha ,\beta ,\gamma ]$ respectively. This law is called composition of quadratic forms.

Brian Conrad's course notes explain this correspondence very satisfyingly without arbitrary base choices. I should also mention Serre's short paper

$\mathrm{\Delta }=b^2-4ac$ which discusses class number

$1$ and related problems.

Isogeny based crypto

We briefly mentioned that rings of integers, orders and their ideals make a remarkable appearance in isogeny theory (and thus isogeny based cryptography). We will sketch this out a little bit.

Note. Luca de Feo has excellent slides, slides and slides that distill the basics of isogeny-based cryptography, and detailed lecture notes. I found the second set of slides (the bold link) particularly useful. Another interesting source discussing the endomorphism rings of elliptic curves is David Kohel's Thesis. Of course any treatise on elliptic curves such as Silverman's The Arithmetic of Elliptic Curves includes a discussion of this topic.

Note. Recall that

$E/{\mathbb{F}}_q$ admits a so-called Frobenius automorphism, which on points

$P=(x,y)\in E$ acts by

${\mathbf{Frob}}_q(P)=(x^q,y^q)$. This acts as the identity on

${\mathbb{F}}_q$-rational points but defines a nontrivial automorphism of the curve^[37].

Note. Recall that isogenies are the "right kind of map" between elliptic curves. They are usually defined in terms of nonconstant morphisms between curves (in the sense of algebraic geometry) that preserve chosen base points. Remarkably, they are always group homomorphisms. The self-isogenies of an elliptic curve

$E$ (along with the constant map to the base point) thus form a ring

$\mathrm{End}(E)$.

In the introduction we wrote that the ring of endomorphisms of an ordinary curve

$E/{\mathbb{F}}_q$ is an order in a quadratic ring of integers. For instance the algebraic relation due to Hasse

$${\mathbf{Frob}}_q^2-t\cdot {\mathbf{Frob}}_q+q\cdot \mathrm{id}=0$$ where

$\mathrm{\#}(E/{\mathbb{F}}_q)=q+1-t$, expresses the fact that the Frobenius endomorphism

${\mathbf{Frob}}_q$ of the curve

$E$ is integral.

$t$ is known as the trace of the Frobenius of

$E/{\mathbb{F}}_q$. It further holds that

$$\mathbb{Z}[{\mathbf{Frob}}_q]\subset \mathrm{End}(E)\subset {\mathcal{O}}_K$$ where

$K$ is the splitting field of

$X^2-tX+1$. When the curve is ordinary

$t$ is coprime to

$q$ and

$K=\mathbb{Q}(D)$ is complex since

$D=t^2-4q<0$ by the Hasse bound.

The ring of endomorphism appears thus as a full rank subring of

${\mathcal{O}}_K$, i.e. an order of

$K$. Orders

$\mathcal{O}$ of quadratic number rings are easy to describe: they are all of the form

$\mathcal{O}=\mathbb{Z}+f{\mathcal{O}}_K$ for a unique positive integer

$f$. Furthermore,

$f$ is the index of the

$\mathcal{O}$ as a subgroup of

${\mathcal{O}}_K$, and

$\mathcal{O}\subset {\mathcal{O}}^{\prime }$ iff

$f^{\prime }\mid f$.

An important property of the trace

$t$ is the

Theorem (Serre-Tate).

$E/{\mathbb{F}}_q$ and

$E^{\prime }/{\mathbb{F}}_q$ are isogenous over

${\mathbb{F}}_q$ iff

$t=t^{\prime }$.

The Serre-Tate theorem tells us that the endomorphism rings of isogenous elliptic curves are all sandwiched between the orders

$\mathbb{Z}[{\mathbf{Frob}}_q]$ and

${\mathcal{O}}_K$ of the same number field

$K$. Futhermore, the previous remark about divisibility of indices implies that there are only finitely many orders in that gap.

On page 6 of Luca de Feo et al.'s paper Towards practical key exchange from ordinary isogeny graphs one finds a description of how (invertible) ideals

$\mathfrak{a}$ of

$\mathcal{O}:=\mathrm{End}(E)$ define finite subgroups

$$E[\mathfrak{a}]=\{P\in E\mid \mathrm{\forall }\phi \in \mathfrak{a},\phi (P)=O\}$$ and associated isognies

$E\twoheadrightarrow \mathfrak{a}\ast E$ where

$\mathfrak{a}\ast E=E/E[\mathfrak{a}]$ is the quotient curve. These isogenies are always horizontal (in the sense of page 66 out of 96 of the bold link) so that

$\mathrm{End}(\mathfrak{a}\ast E)=\mathcal{O}=\mathrm{End}(E)$. It turns out that this defines an action of the class group of invertible ideals of

$\mathcal{O}$ on the isogeny graph of

$E$. One can thus walk along this graph using products of ideals. This is the basis of Diffie-Hellman-type key exchange protocols.

Appendix

Glossary

A ring is an algebraic structure

$R$ in which one can add, subtract and multiply and the usual rules of algebra apply. See wikipedia for a formal definition. The most familiar example is the ring of (rational) integers

$\mathbb{Z}=\{\dots ,-2,-1,0,1,2,3,\dots \}$ with the usual addition and multiplication. Division is usually not possible: for instance

$½\notin \mathbb{Z}$. Of course

$½$ exists as a rational number, but it's not an integer. We say that

$a\in R$ divides

$b\in R$, and we write

$a\mid b$, if there is some

$c\in R$ such that

$a\times c=b$.

The rings in this note are all commutative (for all

$a,b\in R$ it holds that

$a\times b=b\times a$) and unital (there is an element

$1_R$ such that forall

$a\in R$ we have

$1_R\times a=a=a\times 1_R$). When working in a ring one usually drops the "

$\times$" symbol and writes

$ab$ or

$a\cdot b$ in stead of

$a\times b$, also one usually writes

$1$ in stead of

$1_R$.

A domain is a ring where cancellation is true: if

$a\ne 0$ and

$b,c\in R$ satisfy

$a\times b=a\times c$ then

$b=c$. Equivalently it is a ring in which the product of two nonzero elements is again nonzero. Not all rings of interest in cryptography are domains. For instance RSA cryptography works in rings

$R=\mathbb{Z}/N\mathbb{Z}$ of (rational) integers modulo an "RSA modulus"

$N$ (a product of two large distinct primes

$N=pq$). Such rings aren't domains: both

$p$ and

$q$ are nonzero in

$R$, yet their product

$pq$ (which is

$N$) is zero in

$R$. To wit,

$2,3\ne 0$ in

$\mathbb{Z}/6\mathbb{Z}$ yet

$2\cdot 3=0$ in

$\mathbb{Z}/6\mathbb{Z}$.

An element

$a\in R$ is said to be invertible or a unit if there exists

$b\in R$ with

$ab=1$. The set of all units is the group of units of

$R$ is the set of all units of

$R$. It is a group under multiplication, and is sometimes written

$\mathcal{U}(R)$,

${\mathcal{U}}_R$ or even

$R^{\times }$. For instance

• the units of
  $\mathbb{Z}$ are precisely
  $\{-1,+1\}$
• the units of the field of rational numbers
  $\mathbb{Q}$ are all nonzero rational numbers
  ${\mathbb{Q}}^{\times }$
• the units of
  $\mathbb{Z}/7\mathbb{Z}$ are^[38]
  $\{1,2,3,4,5,6\}$ since
  $1\cdot 1=1$,
  $2\cdot 4=1$,
  $3\cdot 5=1$ in
  $\mathbb{Z}/7\mathbb{Z}$
• the units of
  $\mathbb{Z}/12\mathbb{Z}$ are^[39]
  $\{1,5,7,11\}$ since
  $1\cdot 1=1$,
  $5\cdot 5=1$,
  $7\cdot 7=1$ and
  $11\cdot 11=1$ in
  $\mathbb{Z}/12\mathbb{Z}$

Two elements

$x$ and

$y$ in a ring

$R$ are said to be associates if they are the same up to a unit in the sense that there is some unit

$u\in \mathcal{U}(R)$ such that

$y=ux$.

A field is a ring in which every nonzero element has an inverse. Typical examples include the rational numbers

$\mathbb{Q}$, the real numbers

$\mathbb{R}$ and the complex numbers

$\mathbb{C}$. There are also the prime fields

${\mathbb{F}}_p=\mathbb{Z}/p\mathbb{Z}$ for a (rational) prime

$p$ (for instance

$\mathbb{Z}/7\mathbb{Z}$ encountered above) and more generally, the finite fields

${\mathbb{F}}_q$ of size

$q$ where

$q$ is a prime power. Number fields discussed in this text are fields (by definition).

Units and structure of unit groups - classical examples and some facts

There are of course exceptions, and many classical results determining the structure of groups of units of rings.

• ${\mathbb{Z}}^{\times }=\{\pm 1\}$,
• ${\mathbb{Q}}_{+}^{\ast }\simeq \underset{p\text{ prime}}{⨁}\mathbb{Z}$, and taking signs into account,
  ${\mathbb{Q}}^{\ast }\simeq \{\pm 1\}\times {\mathbb{Q}}_{+}^{\ast }$;
• ${\mathbb{R}}_{+}^{\ast }\simeq (\mathbb{R},+)$ via the exponential map / logarithm,
  ${\mathbb{R}}^{\ast }\simeq \{\pm 1\}\times (\mathbb{R},+)$
• $\mathbb{U}=\{z\in \mathbb{C}\mid |z|=1\}$,
  $\mathbb{U}\simeq \mathbb{R}/\mathbb{Z}$ via
  $t\mapsto \exp (2i\pi t)$
• ${\mathbb{C}}^{\ast }\simeq \mathbb{U}\times {\mathbb{R}}_{+}^{\ast }$

For rings of the form

$\mathbb{Z}/N\mathbb{Z}$ it is enough, thanks to the Chinese Remainder Theorem to deal with the prime power case

$N=p^d$:

• if
  $\mathcal{U}(\mathbb{Z}/p^d\mathbb{Z})$ is cyclic isomorphic to
  $\mathbb{Z}/(p-1)p^{d-1}\mathbb{Z}$.

It is a fact that finite subgroups of

$L^{\times }$ (for any field

$L$) are cyclic. As a consequence:

• For any finite field
  ${\mathbb{F}}_q$,
  ${\mathbb{F}}_q^{\times }\simeq \mathbb{Z}/(q-1)\mathbb{Z}$.

If

$A$ is any ring,

$A[X]$ its ring of polynomials,

$P=a_0+a_{1}X+\cdots +a_d{X}^d\in A[X]$, then

• $P$ is invertible in
  $A[X]$ iff
  $a_0$ is invertible in
  $A$ and
  $a_1,\dots ,a_d$ are nilpotent.

In particular, if

$A$ is reduced then

$A[X{]}^{\times }\simeq A^{\times }$.

Likely the most important example on this list is the (noncommutative) ring of matrixes

$M_n(A)$ for a (commutative) ring

$A$: its units are precisely those matrices whose determinant is a unit in

$A$.

---

1. where

   $N=pq$ is the product of two large primes. ↩︎

2. computing their order is equivalent to factoring

   $N=pq$, and is a difficult problem ↩︎

3. to generate two large primes

   $p,q$, their product
   $N=pq$ and be trusted with discarding the factors
   $p$ and
   $q$. ↩︎

4. of Imaginary Quadratic Number Fields

   $K=\mathbb{Q}(\sqrt{d})$,
   $d<0$ ↩︎

5. of quadratic number fields ↩︎

6. discrete, spanning subgroups

   $\mathrm{\Lambda }\subset {\mathbb{R}}^n$. ↩︎

7. and lattice methods play a significant role in ANT. ↩︎

8. no relation with the order a group introduced earlier. ↩︎

9. and which is invariably discussed in pretty much every other text on the subject ↩︎

10. according to Wolfram Alpha,

    $P=X^6+3X^4-4X^3+3X^2+12X+5$ does the job. ↩︎

11. Of characteristic zero ↩︎ ↩︎

12. with rational coefficients ↩︎ ↩︎ ↩︎ ↩︎

13. isomorphic ↩︎

14. That should be an isomorphism

    $K\simeq \mathbb{Q}(\sqrt{d})$ rather than an equality. ↩︎

15. The units of a ring

    $A$ are its invertible elements, i.e. those elements
    $a\in R$ such that there exists
    $b\in R$ with
    $a\times b=1_R$. The units of
    $\mathbb{Z}$ are
    $-1$ and
    $+1$. ↩︎

16. existence of factorizations, that is ↩︎

17. existence of factorizations, that is ↩︎

18. In the same sense as before: up to reordering and up to units. ↩︎

19. (without proof) ↩︎

20. This requires a computation which we skip. ↩︎

21. It is a simple task to verify that these are indeed ideals. ↩︎

22. i.e. the

    ${\mathcal{O}}_K$ are noetherian. Dedekind rings are noetherian by definition. ↩︎

23. For this to work, we should assume

    $R$ to be a domain. ↩︎ ↩︎

24. Prime ideals are usually defined as the ideals

    $I$ of
    $R$ such that the quotient ring
    $R/I$ is a domain. ↩︎

25. and Dedekind domains more generally. ↩︎

26. (up to association) ↩︎ ↩︎

27. Domains with only principal ideals are called Principal Ideal Domains (PID). ↩︎

28. The proof in Baker is surprisingly simple yet quite non-trivial. ↩︎

29. We stole that sentence from A Conversational Introduction to Algebraic Number Theory by ↩︎

30. using the standard characterization of prime ideals as those ideals

    $\mathfrak{p}$ whose quotient ring
    $R/\mathfrak{p}$ is a domain. ↩︎

31. and more generally any Dedekind domain ↩︎

32. euclidean, actually ↩︎

33. and we already explained why back then ↩︎

34. of either elements or ideals ↩︎

35. for all

    $x,y\in \mathbb{Z}$, ↩︎

36. Conventions vary. ↩︎

37. if we consider for instance all

    $\overline{{\mathbb{F}}_q}$-rational points. ↩︎

38. $2\cdot 4=8=1\cdot 7+1\equiv 1\mathrm{mod}7$ so
    $2$ is invertible with inverse
    $4$,
    $3\cdot 5=15=2\cdot 7+1\equiv 1\mathrm{mod}7$ so
    $3$ is invertible with inverse
    $5$,
    $6\cdot 6=36=5\cdot 7+1\equiv 1\mathrm{mod}7$ so
    $6$ is invertible and is its own inverse. ↩︎

39. $5\cdot 5=25=2\cdot 12+1\equiv 1\mathrm{mod}12$ so
    $5$ is invertible and is its own inverse,
    $7\cdot 7=49=4\cdot 12+1\equiv 1\mathrm{mod}12$ so
    $7$ is invertible and is its own inverse,
    $11\cdot 11=121=10\cdot 12+1\equiv 1\mathrm{mod}12$ so
    $11$ is invertible and is its own inverse ↩︎