Try   HackMD
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

OK 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

(Z/NZ)×[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]
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:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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
    OK
    ,
  • as the Log-unit lattice
    LogK(OK×)
    .

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/Fq is an ordinary elliptic curve over a finite field
Fq
, its ring of endomorphisms
O=End(E)
is an order in an imaginary quadratic number field
K=Q(D)
associated to the (isogney class of the) curve
E
. The class group
Cl(O)
of invertible ideals of
End(E)
acts on the isogeny graph of curves defined over
Fq
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.

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

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
    qQ
    , take
    P=XqQ[X]
    ;
  • square roots of rationals "
    q
    " with
    qQ
    , take
    P=X2qQ[X]
    ;
  • higher roots such as "
    ar
    ", take
    P=Xra
    );

and many, many more In particular roots of unity

ζ=exp(2ikπn), with
P=Xn1
, 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

Q of all complex algebraic numbers forms a subfield of
C
.

Note. This is not a priori obvious. Take

α=5+1213: individually
5
and
13
are algebraic (they are roots of
X25
and
X213
respectively). To see that their
Q
-linear combination
α
is algebraic we need to come up with a (nonzero) rational polynomial
P
annihilating
α
. We see that
α2=6112153
so that
α
is a root of
P=(X26112)253=X4616X2+3481144
Since
α
is a root of this rational polynomial, we see that
α
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
α=5+1213
, we see that it is also a root of
144X41464X2+3481Z[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 "

d" for
dZ
is an algebraic integer, as a root of the monic integer polynomial
X2d
, but
23
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

OC of all complex algebraic integers is a subring of
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

23+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:
dimQK<
.

In other words,

K is a field[11:1] and there exist elements
α1,,αdK
such that any element
xK
can be expressed as
x=k=1drkαk
for some rational numbers
r1,,rdQ
. Here
ddimQK
.

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

Q(2)={a+b2a,bQ}orQ(i)={a+bia,bQ} One easily verifies that these subsets of
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
Q[X]
. Consider for instance
P=X4X22
: this polynomial is reducible, as
P=(X2+1)(X22)
. As a consequence it has two qualitatively very different pairs of solutions :
±2
and
±1
. Obviously, "adjoining
2
to
Q
" produces
K=Q[2]
a field that is substantially different from
L=Q[i]
obtained by "adjoining
1
to
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
    2
    and
    2
    apart from one another (the roots of the irreducible rational polynomial
    X22
    ) by algebraic manipulations[12] alone.
  • Neither can you tell any of
    53
    ,
    eiπ353
    and
    eiπ353
    apart from one another (the three roots of the irreducible rational polynomial
    X3+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

2 and
2
behave exactly the same, like some "abstract quantity"
δ
subject to the sole constraint that its square be two (i.e.
δ
is a root of
X22
).

Similarly one might object "

53 is a real number while
eiπ353
and
eiπ353
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"
α
subject only to the constraint that its cube be
5
(i.e.
α
is a root of
X3+5
).

To illustrate this, consider the problem of expressing

1δ+3 as a rational-linear combination of
1
and
δ
alternatively with
δ=2
and
δ=2
. The method is the same in both cases: one multiplies this fraction by the "conjugate quantity" both in the numerator and denominator:

δ=2
δ=2
1δ+3=12+3=2+3(2+3)(2+3)=32=3δ
1δ+3=12+3=2+3(2+3)(2+3)=3+2=3δ

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
Q
. There is a number field
KP
obtained by formally adjoining a root of
P
to
Q
.

One can construct

KP as the quotient ring
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
KP
and
(1,x,,xd1)
forms a
Q
-basis of
KP
where
d=deg(P)
.

Note. In concrete terms this means that one defines

KP as the set of polynomials "mod
P
", and does operations "mod
P
". Thus
A×B
is computed by computing the ordinary product
A×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

C. In particular this point of view makes the following trivial:

Theorem. There are precisely

n field homomorphisms
σ:KPC
.

Indeed, to define such a

σ, it is enough to choose one of
P
's
d
distinct roots
z1,,zdC
and to set
σ(x):=zk
, where
x=X mod P
. This uniquely pins down
σ
.

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

KP-irreducible polynomial
QKP[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

KP for some irreducible rational polynomial
P
.

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

KP,
KQ
and
KR
, where
P=X23
,
Q=X212
and
R=X24X+1
, are isomorphic. This is the reason why one usually insists on square free
d
when defining
Q(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

OK 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
OK
is the subring of all algebraic integers in
K
.

If

K is a concrete subfield of
C
, we have
OK=OCK
. We can restate a previous lemma as

Lemma. The ring of rational integers

OQ is the ring
Z
of ordinary integers.

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

Q is the usual ring of integers
Z
alone would be insufficient grounds to justify calling the other rings
OK
"rings of integers". But the connection runs much deeper. As we will see, these "rings of integers"
OK
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

αK there will exist some positive (rational) integer
c
with
cαOK
. If follows that:

Lemma.

OK spans
K
as a rational vector space.

The additive structure of

OK can be made 100% precise:

Lemma. As an additive group,

OKZn where
n=dimQ(K)
.

One says that

OK is an order of
K
where

Definition. An order of

K is any subgring
RK
which spans
K
and whose additive group is isomorphic to
Zn
.

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
dimQ(K)=2
. If
K
is a quadratic number field, there exists a unique square free integer
dZ{0,1}
such that
K=Q(d)={a+bda,bQ}
[14]. We say that
K=Q(d)
is an imaginary quadratic number field when
d<0
. The ring of integers of
Q(d)
has a simple description depending on the residue of
d
mod
4
:

  • if
    d2,3 mod 4
    then
    OQ(d)={the set of all a+bd where a,bZ}
  • if
    d1 mod 4
    then
    OQ(d)={the set of all a+b1+d2 where a,bZ}

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.

d0 mod 4 is not on the list: if
4=22
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
Q[X]/X2d
so that
X
mod
X2d
is a formal square root of
d
in
K
.

Note. One often sets

τ={dif d2,3 mod 41+d2if d1 mod 4 Then
OK=Z[τ](/vgfFYxLiTPuj4OqmyDLIIw)={a+bτa,bZ}
.

Note. Some values of

d yield familiar numbers:

  • d=+5
    : then
    d1 mod 4
    and
    OK=Z[ϕ]
    where
    ϕ=1+52
    is the golden ratio
  • d=1
    : then
    d3 mod 4
    and
    OK=Z[i]
    are the Gaussian integers
  • d=3
    : then
    d1 mod 4
    and
    OK=Z[j]
    , where
    j=1+i32=exp(2iπ/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/Q has the form
Q(θ)
where
θ
is subject to a relation
θ3+pθ+q
with
p,qQ
and
(27q2+4p3)0
. The latter condition ensures irreducibility of
X3+pX+q
. Explicit integral bases for
K
's ring of integers
OK
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=Q(d3) where
d2
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
Q(ζn)
is the subfield of
C
generated by
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
Z[ζn]={0k<φ(n)akζnk | akZ}.
Here
φ(n)
is Euler's totient function and the degree of the
n
-th cyclotomic polynomial
Φn
, the minimal polynomial of
ζ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=pd
is a prime power and how to derive the general case from there.

Primes and factorization

Number fields

K and their rings of integers
OK
provide a vast generalization of the rational numbers
Q
and rational integers
Z
(note that
OQ=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

Z.

Primes as indivisible elements

Prime numbers are the positive integer

pZ 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
Z
: indeed, all its factorizations
p×1, 1×p, (p)×(1) and (1)×(p)
have one factor that is a unit[15] of
Z
, i.e.
±1
.

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

R (in particular
OK
):

Definition. An nonzero and nonunit element

πR is said to be irreducible if for any factorization
π=a×b
, either
a
or
b
is a unit in
R
.

Thus the primes of

Z are the (positive) irreducible elements of the ring
Z
.

Primes as atoms of multiplication

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

pZ such that whenever
p
divides a product
a×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×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

pR is said to be prime if for any
a,bR
such that
p
divides
a×b
,
p
divides
a
or
p
divides
b
(or both).

Thus the primes of

Z are the (positive) prime elements of the ring
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,} (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

OK. 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

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

xR neither zero nor a unit, there is a positive integer
n
and irreducibles
π1,,πn
such that
x=i=1nπi
. The reader doesn't have to know what 'noetherian domains' are, it is enough to know that the rings of integers
OK
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

xR (nonzero and not a unit) has a factorization
x=i=1rpi
into a product of primes and if
x=i=1sqi
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
u1,,ur
of
R
such that
qi=uipi
for all
i=1,2,,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

OK 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
Z
is uniqueness; half the battle is won!

But that hope is soon squashed: some rings of integers

OK contain irreducibles that fail to be prime. Examples are a dime a dozon. Consider
K=Q(5)
, since
53 mod 4
, we have
OK=Z[5]={a+b5a,bZ}
. The number
6OK
has two essentially distinct factorizations into irreducibles:
2×3=6=(1+5)×(15)
One shows that
2,3,(1+5)
and
(15)
are irreducible[20] but not prime as neither
2
nor
3
divide either
(1+5)
or
(15)
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
IR
such that for all
xI
and
rR
the product
rx
is again in
I
.

In other words, an ideal

I is a (nonempty) subset of
R
such that if
x,yI
and
rR
, then
x±yI
and
rxI
. 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

x1,,xmR, we define
x1,,xm={k=1mrkxk | r1,,rmR}

Sets of the form

x1,,xmR are called finitely generated ideals[21]. In general rings there will be ideals that are not finitely generated, but in rings of integers
OK
, all ideals are finitely generated[22]. Ideals of the form
x
(i.e. generated by a single element) are called principal ideals.

If

IOK is a nonzero ideal and
αI0
, then
αOK=αI
shows that
I
is a full rank additive subgroup of
OK
. As such, general results about subroups of
Zn(OK)
impose that

Lemma.

(I,+) is isomorphic to
Zn
.

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
  • a,b,c
    do too
  • The letters
    p,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 where xI,yJ}.
Product of ideals. Define
IJ={ixiyi where xiI,yiJ}
.
Divisibility. Define
I
divides
J
, and write
IJ
, if there is an ideal
K
with
IK=J
.
Intersection of ideals. The intersection
IJ
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:

{Commutativity: IJ=JIandI+J=J+I,Associativity: (IJ)K=I(JK)and(I+J)+K=I+(J+K),Distributivity: (I+J)K=IK+JK

Note. One has

x1,,xn=i=1nxi and
xi1inyj1jm=xiyj1in, 1jm
.

Relating operations on elements to operations on ideals

In a ring

R we can convert elements into (principal) ideals. Recall
x={rxrR}
.
:{R0{set of all nonzero prin-cipal ideals of R}xx
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,bR
    are associates iff
    a=b
  • uR
    is a unit iff
    u=R
  • a
    divides
    b
    iff
    ba

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:

IJ when there exists an ideal
K
such that
IK=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
JI
, can be seen as a weaker form of divisibility. Indeed,

Lemma. For arbitrary ideals

I,J in a ring
R
one has
IJJI

Let us introduce nonstandard notation

weak and
strong
to mean respectively

  • IweakJJI
  • IstrongJIJK, IK=J
    .

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

Lemma.

IstrongJIweakJ.

When restricted to principal ideals

a=a and
b=b
the two notions coincide:

Lemma.

astrongbbweakaab.

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=Z[X] of polynomials with (rational) integer coefficients. Consider the three ideals
I=2,X
,
J=2
and
J=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
    is the ideal of all polynomials whose constant term is
    0
    .

Then

J,JI i.e.
IweakJ,J
, yet no ideal
K
can satisfy either
IK=J
or
IK=J
, i.e. neither
IstrongJ
nor
IstrongJ
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

p is prime if for any ideals
I,J
of
R
,
IJpIp
or
Jp
.

In other words,

p prime ideal of R(for all ideals I,J,pweakIJpweakI or pweakJ)

This shows the connection with the notion of prime elements:

p prime element of R( for all a,bR,pabpa or pb)

The connection is further strenghtened by

Lemma. Let

pR 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

OK[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

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
OK
for arbitrary number fields
K
.

Drawing Inspiration from the Integers

Recall the notation

a={akkZ}. 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
Z
, there exists a unique nonnegative integer
n
with
I=n
. As a consequence,
weak
and
strong
are the same.

Z
With elements With Ideals
Division
ab
aweakbastrongb} same thing
Associates
b=ua
for
uU(Z)
a=b
Product
ac=b
ac=b
GCD
d=gcd(a,b)
d=a+b
LCM
m=lcm(a,b)
m=ab
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
n=i=1rpimi
Every nonzero ideal
I=n
has a unique factorization into a product of prime ideals
I=n=i=1rpimi

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

OK of number fields
K
. We state it without proof, along the intermediary result that
weak
and
strong
are identical relations.

OK
With elements With Ideals
Division
ab
IweakJIstrongJ} same thing
Associates
b=ua
for
uU(OK)
I=J
Product
ac=b
IJ
GCD doesn't usually exist
I+J
LCM doesn't usually exist
IJ
Primes prime elements nonzero prime ideals
p
Set of Primes
{primes p up to association}
{ principal prime ideals p}{ all nonzero prime ideals p}
FTA usually wrong Every nonzero ideal
I
has a unique factorization into a product of prime ideals
I=i=1rpimi

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
OK
.

Theorem. There exists a nonzero ideal

J such that
IJ
is principal.

In other words, all (nonzero) ideals in

OK are invertible. With this result in hand, it is pleasantly easy to derive the following propositions. Let
a,b,c
be nonzero ideals in
OK
.

Cancellation.

ab=acb=c.
To contain is to divide[29].
abba
that is
astrongbaweakb

Finite set of divisors. There are only finitely many ideals dividing a given ideal
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×3=6=(15)(1+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
OK=Z[5]
of
K=Q(5)
has an integral power basis
(1,τ)
, where
τ=5
, one may deduce from the factorizations
X2+5=(X+1)2 mod [2]
and
X2+5=(X+1)(X1) mod [3]
of
τ
's minimal polynomial
X2+5
the factorizations
2=2,1+52and3=3,1+53,15
Furthermore, the ideals
2,1+5
,
3,1+5
and
3,15
are prime (indeed, maximal) by inspection[30]:
OK/2,1+5F2andOK/3,1±5F3

We also get the prime factorizations of

1+5 and
15
:
2,1+53,1+5=6,2(1+5),3(1+5),(1+5)2=1+5
and, given that
2,1+5=2,15
,
2,153,15=6,2(15),3(15),(15)2=15

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
I(R)
of nonzero ideals along with ideal multiplication "
" forms a commutative monoid with unit
1=R
. Recall that a (commutative) monoid is a set
M
with a multiplication "
:M×MM
" which is (commutative) associative and unital. The subset
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
IJ
principal.

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

OK 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
OK
of a number field
K
, its monoid of ideals
I(OK)
has special properties:

  • every ideal
    II(OK)
    is "invertible mod
    P(OK)
    ", in the sense that there exists
    JI(OK)
    with
    IJP(OK)
    .
  • I(OK)
    is cancellative in the sense that
    IJ=IJJ=J
    ,
  • furthermore, its structure is exceedingly simple:
    (I(OK),)(pN,+)I(νp(I))p

Where

νp(I) denotes the multiplicity of
p
in
I
: if
I=i=1rpimi
is the decomposition of
I
into a product of prime ideals, then
for all nonzero prime ideals p,νp(I)={mi if p=pi0 otherwise
In other words,
I(OK)
is the free monoid on the set of nonzero prime ideals.

Note. In the special case

K=Q and
OK=Z
, the monoid of nonzero ideals is isomorphic to the monoid of positive integers
N0
under multiplication and the previous isomorphism is
(N0,×)(p primeN,+)

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)

OK-submodules
M
of the
OK
-module
K
with the property that for some
xK
,
xMOK
.

Note. In the special case

K=Q and
OK=Z
, fractional ideals are of the form
qZQ
, for some positive rational number
q
. The group of nonzero fractional ideals is thus isomorphic to the group of positive rationals
Q+
under multiplication and the previous isomorphism is
(Q+,×)(p primeZ,+)

Ideal Class group of a ring of integers

We described how to associate to

OK the group of its "fractional ideals"
FI(OK)
and the subgroup of its "principal fractional ideals"
FP(OK)
. This produces two short exact sequences
1U(K)K× x  x FP(OK)1
and
1FP(OK)FI(OK)Cl(OK)1
where, by definition:

Definition.

OK's ideal class group
Cl(OK)
is the quotient group
FI(OK)/FP(OK)
.

It is a simple fact that the ring of integers

OK of a number field
K
[31] is a PID iff it is a UFD. Also,
OK
is a PID iff
I(OK)=P(OK)
iff
FI(OK)=FP(OK)
iff
Cl(OK)={1}
. Thus

Theorem. Are equivalent: (i)

OK is a PID (ii)
OK
is a UFD (iii)
Cl(OK)
is trivial.

Non Examples. The rings

Z of rational integers,
Z[i]
of Gaussian integers and
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

Cl(OK) is generated by the (nonzero) prime ideals
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

Z[5] is (isomorphic to)
Z/2Z
and generated by any one of the three ideals
2,1+5
,
3,1+5
or
3,15
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
U(R)
are even rarer.

It is then remarkable that for rings of integers

OK of number fields
K
both of these exist:

Lemma. An algebraic integer

αOK is a unit iff its norm
NK/Q(α)
is
±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

NK/Q and trace
TrK/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=dimQ(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
σ:KC
, say
σ1,,σn
. Such an embedding is called real if it takes
K
to a subfield of the real numbers, and complex otherwise. If
σ
is complex, then composing it with complex conjugation yields a different embedding
σ
. 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

U(OK) is isomorphic to
μK×Zr
, where
μK
is the (finite cyclic) group of roots of unity of
K
and
r=s+t1 (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=Q(d)=Q[X]/X2d for some squarefree integer
d
. We use the notation
OK=Z[τ]
introduced in a previous section. There are two cases to distinguish:

  • d1: then
    s=0
    ,
    t=1
    and the two embeddings are defined by
    τ±i|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
      τ=i
      and
      U(Z[i])={±1,±i}Z/4Z
      ,
    • d=3
      , then
      τ=j=exp(2iπ/3)
      and
      U(Z[j])={±1,±j,±j}Z/6Z
      .
  • d2: In that case
    s=2
    ,
    t=0
    , the two embeddings being defined by
    X±d
    . The roots of unity of
    K
    are
    {±1}
    . We have
    r=1
    and there is a so-called fundamental unit
    ϵOK
    such that all units are of the form
    ±ϵm
    , for
    mZ
    .

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
d2,3 mod [4]
, set
D=4d
, if
d1 mod [4]
, set
D=d
. This time the object of interest are binary quadratic forms, that is: homogeneous degree two polynomial maps
f:Z×ZZ
of the form
f(x,y)=ax2+bxy+cy2
[35] with discriminant equal to
D
, i.e. satisfying
b24ac=D
[36]. We conflate
f
with the vector
[a,b,c]
.

The prime example turns out to come from

OK,
K=Q(d)
: the norm
NK/Q
restricted to the ring
OK
. Recall that its underlying additive group is isomorphic as a group to
Z2
, explicitely by choosing the
Z
-basis
(1,τ)
. One computes the norm in these coordinates:
NK/Q(x+yτ)=(x+yτ)(x+yτ)={x2dy2if d2,3 [4]x2+xy+1d4y2if d1 [4]
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=(stuv)
(i.e.
s,t,u,vZ
,
svtu=1
) such that
fU=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
Cl(d)
. Furthermore, this one to one correspondence is the shadow of a beautiful map that sends (nonzero) ideals
I
of
OK
to the quadratic space
(I,qI)
, where
qI
is simply the (suitably normalized) restriction of the norm form
NK/Q
to
I
!
{nonzero ideals of OK}{quadratic forms on Z2with discriminant D}I(I,qI)\colorred \colorred \colorred\colorred \colorred \colorredCl(d){equivalence classes ofbinary quadratic forms}[I][iso. class of (I,qI)]

(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)

(OK,NK/Q) corresponds to the neutral element
[1]=[OK]
, and there are explicit algebraic formulas for computing the product of two representatives forms represented by
[a,b,c]
and
[α,β,γ]
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

Δ=b24ac 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/Fq admits a so-called Frobenius automorphism, which on points
P=(x,y)E
acts by
Frobq(P)=(xq,yq)
. This acts as the identity on
Fq
-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
End(E)
.

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

E/Fq is an order in a quadratic ring of integers. For instance the algebraic relation due to Hasse
Frobq2tFrobq+qid=0
where
#(E/Fq)=q+1t
, expresses the fact that the Frobenius endomorphism
Frobq
of the curve
E
is integral.
t
is known as the trace of the Frobenius of
E/Fq
. It further holds that
Z[Frobq]End(E)OK
where
K
is the splitting field of
X2tX+1
. When the curve is ordinary
t
is coprime to
q
and
K=Q(D)
is complex since
D=t24q<0
by the Hasse bound.

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

OK, i.e. an order of
K
. Orders
O
of quadratic number rings are easy to describe: they are all of the form
O=Z+fOK
for a unique positive integer
f
. Furthermore,
f
is the index of the
O
as a subgroup of
OK
, and
OO
iff
ff
.

An important property of the trace

t is the

Theorem (Serre-Tate).

E/Fq and
E/Fq
are isogenous over
Fq
iff
t=t
.

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

Z[Frobq] and
OK
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

a of
O:=End(E)
define finite subgroups
E[a]={PEφa, φ(P)=O}
and associated isognies
EaE
where
aE=E/E[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
End(aE)=O=End(E)
. It turns out that this defines an action of the class group of invertible ideals of
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
Z={,2,1,0,1,2,3,}
with the usual addition and multiplication. Division is usually not possible: for instance
½Z
. Of course
½
exists as a rational number, but it's not an integer. We say that
aR
divides
bR
, and we write
ab
, if there is some
cR
such that
a×c=b
.

The rings in this note are all commutative (for all

a,bR it holds that
a×b=b×a
) and unital (there is an element
1R
such that forall
aR
we have
1R×a=a=a×1R
). When working in a ring one usually drops the "
×
" symbol and writes
ab
or
ab
in stead of
a×b
, also one usually writes
1
in stead of
1R
.

A domain is a ring where cancellation is true: if

a0 and
b,cR
satisfy
a×b=a×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=Z/NZ
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,30
in
Z/6Z
yet
23=0
in
Z/6Z
.

An element

aR is said to be invertible or a unit if there exists
bR
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
U(R)
,
UR
or even
R×
. For instance

  • the units of
    Z
    are precisely
    {1,+1}
  • the units of the field of rational numbers
    Q
    are all nonzero rational numbers
    Q×
  • the units of
    Z/7Z
    are[38]
    {1,2,3,4,5,6}
    since
    11=1
    ,
    24=1
    ,
    35=1
    in
    Z/7Z
  • the units of
    Z/12Z
    are[39]
    {1,5,7,11}
    since
    11=1
    ,
    55=1
    ,
    77=1
    and
    1111=1
    in
    Z/12Z

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
uU(R)
such that
y=ux
.

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

Q, the real numbers
R
and the complex numbers
C
. There are also the prime fields
Fp=Z/pZ
for a (rational) prime
p
(for instance
Z/7Z
encountered above) and more generally, the finite fields
Fq
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.

  • Z×={±1}
    ,
  • Q+p primeZ
    , and taking signs into account,
    Q{±1}×Q+
    ;
  • R+(R,+)
    via the exponential map / logarithm,
    R{±1}×(R,+)
  • U={zC|z|=1}
    ,
    UR/Z
    via
    texp(2iπt)
  • CU×R+

For rings of the form

Z/NZ it is enough, thanks to the Chinese Remainder Theorem to deal with the prime power case
N=pd
:

  • if
    U(Z/pdZ)
    is cyclic isomorphic to
    Z/(p1)pd1Z
    .

It is a fact that finite subgroups of

L× (for any field
L
) are cyclic. As a consequence:

  • For any finite field
    Fq
    ,
    Fq×Z/(q1)Z
    .

If

A is any ring,
A[X]
its ring of polynomials,
P=a0+a1X++adXdA[X]
, then

  • P
    is invertible in
    A[X]
    iff
    a0
    is invertible in
    A
    and
    a1,,ad
    are nilpotent.

In particular, if

A is reduced then
A[X]×A×
.

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

Mn(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=Q(d),
    d<0
    ↩︎

  5. of quadratic number fields ↩︎

  6. discrete, spanning subgroups

    ΛRn. ↩︎

  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=X6+3X44X3+3X2+12X+5 does the job. ↩︎

  11. Of characteristic zero ↩︎ ↩︎

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

  13. isomorphic ↩︎

  14. That should be an isomorphism

    KQ(d) rather than an equality. ↩︎

  15. The units of a ring

    A are its invertible elements, i.e. those elements
    aR
    such that there exists
    bR
    with
    a×b=1R
    . The units of
    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

    OK 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

    p whose quotient ring
    R/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,yZ, ↩︎

  36. Conventions vary. ↩︎

  37. if we consider for instance all

    Fq-rational points. ↩︎

  38. 24=8=17+11 mod 7 so
    2
    is invertible with inverse
    4
    ,
    35=15=27+11 mod 7
    so
    3
    is invertible with inverse
    5
    ,
    66=36=57+11 mod 7
    so
    6
    is invertible and is its own inverse. ↩︎

  39. 55=25=212+11 mod 12 so
    5
    is invertible and is its own inverse,
    77=49=412+11 mod 12
    so
    7
    is invertible and is its own inverse,
    1111=121=1012+11 mod 12
    so
    11
    is invertible and is its own inverse ↩︎