study notes
class groups
number theory
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 in number fields . These are objects borrowed from the realm of algebraic number theory (ANT). Topics derived from their study that have found application in cryptography include:
and to a lesser extent (it seems),
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, …
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 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 [1] provide an alternative family of GUOs[2]. However, generating RSA moduli requires either a trusted party[3] or a non-trivial multiparty computation. Generating class groups[4] on the other hand "only" requires generating large negative square free public integers . Taking for a large prime 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:
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:
Orders[8] and rings of integers also make a double-take-worthy appearance in isogeny-based cryptography, a subdomain of elliptic curve cryptography. When is an ordinary elliptic curve over a finite field , its ring of endomorphisms is an order in an imaginary quadratic number field associated to the (isogney class of the) curve . The class group of invertible ideals of acts on the isogeny graph of curves defined over isogenous to (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.
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.
In this section we define (complex) algebraic integers. In the sequel we will restrict to those algebraic integers that reside in small subfields of or, more generally, in abstract number fields.
Complex algebraic numbers are those complex numbers that satisfy a polynomial equation with rational coefficients, i.e. a complex number is algebraic if it satisfies for a (nonzero) polynomial with rational coefficients. Examples include:
and many, many more … In particular roots of unity , with , are algebraic numbers.
Note. Not all complex numbers are algebraic. Those that aren't are called transcendental.
It is a fact that the sum, product and quotient of algebraic numbers is still algebraic.
Theorem. The set of all complex algebraic numbers forms a subfield of .
Note. This is not a priori obvious. Take : individually and are algebraic (they are roots of and respectively). To see that their -linear combination is algebraic we need to come up with a (nonzero) rational polynomial annihilating . We see that so that is a root of 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 killing a particular algebraic number, we may assume the polynomials to have integer coefficients. For instance, returning to , we see that it is also a root of
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 "" for is an algebraic integer, as a root of the monic integer polynomial , but is not.
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 of all complex algebraic integers is a subring of .
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 from scratch. It's doable, but it's painful[10] : )
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 (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
Definition. A number field is a field[11] that is also a finite dimensional rational vector space: .
In other words, is a field[11:1] and there exist elements such that any element can be expressed as for some rational numbers . Here .
Elementary linear algebra shows that
Lemma. All elements of a number field are algebraic.
Examples are plentiful. For instance subfields of the complex numbers such as One easily verifies that these subsets of are subfields: they are stable under addition and product, contain the unit , 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.
When adjoining roots of polynomial equations one should restrict to irreducible polynomials, i.e. polynomials that can't substantially be factored over . Consider for instance : this polynomial is reducible, as . As a consequence it has two qualitatively very different pairs of solutions : and . Obviously, "adjoining to " produces a field that is substantially different from obtained by "adjoining to ". To wit: is a square in but not in .
The complex roots of a given irreducible rational polynomial are absolutely indistinguishable from an algebraic point of view.
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 and behave exactly the same, like some "abstract quantity" subject to the sole constraint that its square be two (i.e. is a root of ).
Similarly one might object " is a real number while and 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 (i.e. is a root of ).
To illustrate this, consider the problem of expressing as a rational-linear combination of and alternatively with and . The method is the same in both cases: one multiplies this fraction by the "conjugate quantity" both in the numerator and denominator:
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 be an irreducible polynomial over . There is a number field obtained by formally adjoining a root of to .
One can construct as the quotient ring of rational polynomials modulo . This produces a number field called the rupture field of . Indeed, if one defines to be the class of mod , then is a root of in and forms a -basis of where .
Note. In concrete terms this means that one defines as the set of polynomials "mod ", and does operations "mod ". Thus is computed by computing the ordinary product , doing long division by 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 . In particular this point of view makes the following trivial:
Theorem. There are precisely field homomorphisms .
Indeed, to define such a , it is enough to choose one of 's distinct roots and to set , where . This uniquely pins down .
One can iterate this construction by adjoining a formal root of any -irreducible polynomial , 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 for some irreducible rational polynomial .
Note. Distinct irreduible polynomials can produce identical[13] number fields. For instance the fields , and , where , and , are isomorphic. This is the reason why one usually insists on square free when defining : the square part of is irrelevant.
In this section we introduce the main object of study of this note: the ring of integers of a number field.
We stated earlier that all elements in a number field are algebraic. Algebraic integers in are far rarer. The ring of algebraic integers of a number field is the central object in these notes.
Definition. Let be a number field. Its ring of integers is the subring of all algebraic integers in .
If is a concrete subfield of , we have . We can restate a previous lemma as
Lemma. The ring of rational integers is the ring of ordinary integers.
Note. The fact that the (so-called) ring of integers of is the usual ring of integers alone would be insufficient grounds to justify calling the other rings "rings of integers". But the connection runs much deeper. As we will see, these "rings of integers" 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 there will exist some positive (rational) integer with . If follows that:
Lemma. spans as a rational vector space.
The additive structure of can be made 100% precise:
Lemma. As an additive group, where .
One says that is an order of where
Definition. An order of is any subgring which spans and whose additive group is isomorphic to .
As with any new definition, one's first instinct should be to try to understand some simple examples. But…
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 are fields with . If is a quadratic number field, there exists a unique square free integer such that [14]. We say that is an imaginary quadratic number field when . The ring of integers of has a simple description depending on the residue of mod :
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. is not on the list: if divides , then isn't square free.
Note. Keeping in line with the more formal point of view, one can cleanly define as so that mod is a formal square root of in .
Note. One often sets Then .
Note. Some values of yield familiar numbers:
The next simplest case after quadratic extensions are cubic extensions. This is where things start to get complicated, truly complicated. The general cubic extension has the form where is subject to a relation with and . The latter condition ensures irreducibility of . Explicit integral bases for 's ring of integers 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 where 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.
The -th cyclotomic field is the subfield of generated by and a primitive -th root of unity. Alternatively it is the splitting field of the -th cyclotomic polynomial. Its ring of integers is Here is Euler's totient function and the degree of the -th cyclotomic polynomial , the minimal polynomial of . This isn't an easy result. Baker's account of the case where is prime is good. In the comments to this MO answer, Keith Conrad sketches an argument for the case is a prime power and how to derive the general case from there.
Number fields and their rings of integers provide a vast generalization of the rational numbers and rational integers (note that ). 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.
There are two equivalent but conceptually different ways to think of prime numbers in .
Prime numbers are the positive integer that possess precisely two distint positive integer factors: and themselves. Another way of saying the same thing is that possesses no interesting factorization in : indeed, all its factorizations have one factor that is a unit[15] of , i.e. .
We can use this as the template for a definition in an arbitrary ring (in particular ):
Definition. An nonzero and nonunit element is said to be irreducible if for any factorization , either or is a unit in .
Thus the primes of are the (positive) irreducible elements of the ring .
Primes also play a basic role in factoring numbers. A (rational) prime is a positive integer such that whenever divides a product of integers , it has to divide either or (and possibly both). Thus isn't prime since divides yet does not divide either or .
We can similarly use this as the template for a definition in an arbitrary ring :
Definition. A nonzero and nonunit element is said to be prime if for any such that divides , divides or divides (or both).
Thus the primes of are the (positive) prime elements of the ring .
When working over the integers, irreducibles and primes coincide. They give rise to the same set of (positive) prime numbers (if we restrict attention to the positive ones). Furthermore, we have the
FTA. Any positive integer has a unique factorization as a product of primes.
This is the sort of theorem that we want to generalize to rings of integers . 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.
In a domain, all primes are irreducible. But in general there may be irreducibles that are not prime. In (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 be a noetherian domain. Every nonzero nonunit of can be expressed as a finite product of irreducibles.
Using slightly more symbols, for neither zero nor a unit, there is a positive integer and irreducibles such that . The reader doesn't have to know what 'noetherian domains' are, it is enough to know that the rings of integers 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 be a domain. Factorizations into product of primes, when they exist, are essentially unique.
To make that statement slightly more precise, if (nonzero and not a unit) has a factorization into a product of primes and if is yet another factorization of into a product of primes, then and (up to a permutation of the indices) there are units of such that for all .
A domain that satisfies the fundamental theorem of algebra is called a Unique Factorization Domain, UFD for short:
Definition. A Unique Factorization Domain is a domain 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 be a domain s.t. every nonzero nonunit element has a factorization as a product of irreducibles. Then is a UFD iff all its irreducibles are prime.
This shows that a necessary condition for the FTA to hold in a ring is that irreducibles and primes be the same. Proofs of these propositions can be found in this note.
We claimed earlier[19] that all 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 is uniqueness; half the battle is won!
But that hope is soon squashed: some rings of integers contain irreducibles that fail to be prime. Examples are a dime a dozon. Consider , since , we have . The number has two essentially distinct factorizations into irreducibles: One shows that and are irreducible[20] but not prime as neither nor divide either or and vice versa.
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.
We can restate prime-ness, divisibility, unique factorization etc… in a ring in terms not of the elements of but in terms of the ideals of .
Definition. An ideal in a ring is an additive subgroup such that for all and the product is again in .
In other words, an ideal is a (nonempty) subset of such that if and , then and . 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 , we define
Sets of the form are called finitely generated ideals[21]. In general rings there will be ideals that are not finitely generated, but in rings of integers , all ideals are finitely generated[22]. Ideals of the form (i.e. generated by a single element) are called principal ideals.
If is a nonzero ideal and , then shows that is a full rank additive subgroup of . As such, general results about subroups of impose that
Lemma. is isomorphic to .
Note. The so-called trivial ideals are the zero ideal and itself: .
Note. There are varying nontational conventions for ideals…
Let be ideals in some ring . The following operations define new ideals of .
Sum of ideals. Define .
Product of ideals. Define .
Divisibility. Define divides , and write , if there is an ideal with .
Intersection of ideals. The intersection 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:
Note. One has and .
In a ring we can convert elements into (principal) ideals. Recall . 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: iff[23] and are associates, i.e. there exists a unit with . 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 [23:1].
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.
The most natural way to define divisibility for ideals is in terms of products: when there exists an ideal such that . 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 , can be seen as a weaker form of divisibility. Indeed,
Lemma. For arbitrary ideals in a ring one has
Let us introduce nonstandard notation and to mean respectively
Using this notation we can re-state the previous lemma:
Lemma. .
When restricted to principal ideals and the two notions coincide:
Lemma. .
For non principal ideals (and arbitrary rings) the previous equivalence usually fails. Consider for instance the ring of polynomials with (rational) integer coefficients. Consider the three ideals , and . One easily sees that
Then i.e. , yet no ideal can satisfy either or , i.e. neither nor hold.
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 be a ring.
Definition. An ideal is prime if for any ideals of , or .
In other words,
This shows the connection with the notion of prime elements:
The connection is further strenghtened by
Lemma. Let be a nonzero nonunit: is prime iff is a prime ideal.
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 [25].
To summarize, we can consider, in a domain ,
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 (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).
We will first recast the Fundamental Theorem of Arithmetic (FTA) of the integers in terms of ideals and their unique factorization into products of prime ideals. We then state (without proof) its extension to rings of integers for arbitrary number fields .
Recall the notation . The ring of (rational) integers is particular in the sense that all its ideals are principal[27]. In other words, if is an ideal of , there exists a unique nonnegative integer with . As a consequence, and are the same.
With elements | With Ideals | |
---|---|---|
Division | ||
Associates | for | |
Product | ||
GCD | ||
LCM | ||
Primes | prime numbers | nonzero prime ideals |
Set of Primes | all positive primes | all nonzero prime ideals |
FTA | Every positive integer has a unique factorization into a product of primes | Every nonzero ideal has a unique factorization into a product of prime ideals |
Note. GCD = greatest common divisor, LCM = lowest common multiple, FTA = Fundamental Theorem of Algebra.
As promised, here (in the last box) is the version of the FTA for rings of integers of number fields . We state it without proof, along the intermediary result that and are identical relations.
With elements | With Ideals | |
---|---|---|
Division | ||
Associates | for | |
Product | ||
GCD | doesn't usually exist | |
LCM | doesn't usually exist | |
Primes | prime elements | nonzero prime ideals |
Set of Primes | ||
FTA | usually wrong | Every nonzero ideal has a unique factorization into a product of prime ideals |
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 be any nonzero ideal in .
Theorem. There exists a nonzero ideal such that is principal.
In other words, all (nonzero) ideals in are invertible. With this result in hand, it is pleasantly easy to derive the following propositions. Let be nonzero ideals in .
Cancellation. .
To contain is to divide[29]. that is
Finite set of divisors. There are only finitely many ideals dividing a given ideal .
FTA. Every nonzero ideal is uniquely the product of finitely many prime ideals.
We revisit the unfortunate situation mentioned earlier. The point of view described here is to factor the principal ideals and . Using the fact that the ring of integers of has an integral power basis , where , one may deduce from the factorizations and of 's minimal polynomial the factorizations Furthermore, the ideals , and are prime (indeed, maximal) by inspection[30]:
We also get the prime factorizations of and : and, given that ,
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 . We state (without proof) the decidedly non trivial fact that this group is always finite.
In any domain , the set of nonzero ideals along with ideal multiplication "" forms a commutative monoid with unit . Recall that a (commutative) monoid is a set with a multiplication "" which is (commutative) associative and unital. The subset of all (nonzero) principal ideals forms a submonoid.
Definition. A (nonzero) ideal of is said to be invertible if there exists with principal.
The "main ingredient" from two sections ago states that all (nonzero) ideals in for a number field are invertible. Also, the results on existence and uniqueness of factorizations into prime ideals tells us that when is the ring of integers of a number field , its monoid of ideals has special properties:
Where denotes the multiplicity of in : if is the decomposition of into a product of prime ideals, then In other words, is the free monoid on the set of nonzero prime ideals.
Note. In the special case and , the monoid of nonzero ideals is isomorphic to the monoid of positive integers under multiplication and the previous isomorphism is
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) -submodules of the -module with the property that for some , .
Note. In the special case and , fractional ideals are of the form , for some positive rational number . The group of nonzero fractional ideals is thus isomorphic to the group of positive rationals under multiplication and the previous isomorphism is
We described how to associate to the group of its "fractional ideals" and the subgroup of its "principal fractional ideals" . This produces two short exact sequences and where, by definition:
Definition. 's ideal class group is the quotient group .
It is a simple fact that the ring of integers of a number field [31] is a PID iff it is a UFD. Also, is a PID iff iff iff . Thus
Theorem. Are equivalent: (i) is a PID (ii) is a UFD (iii) is trivial.
Non Examples. The rings of rational integers, of Gaussian integers and 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 is generated by the (nonzero) prime ideals . 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 is (isomorphic to) and generated by any one of the three ideals , or we encountered earlier.
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 explicit descriptions of its units are rare, and explicit descriptions of the structure of unit groups are even rarer.
It is then remarkable that for rings of integers of number fields both of these exist:
Lemma. An algebraic integer is a unit iff its norm is .
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 and trace 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 associated with the number field . Let be 's dimension as a rational vector space. It follows from the Primitive Element Theorem quoted above[33] that there are distinct field embeddings , say . Such an embedding is called real if it takes 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 number of real embeddings of , number of complex embeddings of . Note that .
Dirichlet's Unit Theorem. The unit group is isomorphic to , where is the (finite cyclic) group of roots of unity of and .
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.
The only situation that is easy enough for me to describe explicitely is that of quadratic number fields for some squarefree integer . We use the notation introduced in a previous section. There are two cases to distinguish:
: then , and the two embeddings are defined by . Then and the unit group is a finite, cyclic group of roots of unity in . For all except and the unit group is ; the nontrivial cases are
: In that case , , the two embeddings being defined by . The roots of unity of are . We have and there is a so-called fundamental unit such that all units are of the form , for .
This recovers the classical resolution of the so-called Pell equation, see in particular this section.
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.
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.
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 and an associated quantity called the "discriminant": if , set , if , set . This time the object of interest are binary quadratic forms, that is: homogeneous degree two polynomial maps of the form [35] with discriminant equal to , i.e. satisfying [36]. We conflate with the vector .
The prime example turns out to come from , : the norm restricted to the ring . Recall that its underlying additive group is isomorphic as a group to , explicitely by choosing the -basis . One computes the norm in these coordinates: This defines a binary quadratic form and one easily checks its discriminant equals .
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 if there exists a (direct) base change matrix (i.e. , ) such that . There are only finitely many equivalence classes of forms.
It turns out that (at least when ) this finite set of equivalence classes is in one to one correspondence with the class group . Furthermore, this one to one correspondence is the shadow of a beautiful map that sends (nonzero) ideals of to the quadratic space , where is simply the (suitably normalized) restriction of the norm form to !
(To be fair, the proper target of the first map is the category of oriented quadratic planes: free abelian groups of rank with an orientation and a quadratic form of discriminant , 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) corresponds to the neutral element , and there are explicit algebraic formulas for computing the product of two representatives forms represented by 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 which discusses class number and related problems.
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 admits a so-called Frobenius automorphism, which on points acts by . This acts as the identity on -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 (along with the constant map to the base point) thus form a ring .
In the introduction we wrote that the ring of endomorphisms of an ordinary curve is an order in a quadratic ring of integers. For instance the algebraic relation due to Hasse where , expresses the fact that the Frobenius endomorphism of the curve is integral. is known as the trace of the Frobenius of . It further holds that where is the splitting field of . When the curve is ordinary is coprime to and is complex since by the Hasse bound.
The ring of endomorphism appears thus as a full rank subring of , i.e. an order of . Orders of quadratic number rings are easy to describe: they are all of the form for a unique positive integer . Furthermore, is the index of the as a subgroup of , and iff .
An important property of the trace is the
Theorem (Serre-Tate). and are isogenous over iff .
The Serre-Tate theorem tells us that the endomorphism rings of isogenous elliptic curves are all sandwiched between the orders and of the same number field . 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 of define finite subgroups and associated isognies where is the quotient curve. These isogenies are always horizontal (in the sense of page 66 out of 96 of the bold link) so that . It turns out that this defines an action of the class group of invertible ideals of on the isogeny graph of . One can thus walk along this graph using products of ideals. This is the basis of Diffie-Hellman-type key exchange protocols.
A ring is an algebraic structure 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 with the usual addition and multiplication. Division is usually not possible: for instance . Of course exists as a rational number, but it's not an integer. We say that divides , and we write , if there is some such that .
The rings in this note are all commutative (for all it holds that ) and unital (there is an element such that forall we have ). When working in a ring one usually drops the "" symbol and writes or in stead of , also one usually writes in stead of .
A domain is a ring where cancellation is true: if and satisfy then . 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 of (rational) integers modulo an "RSA modulus" (a product of two large distinct primes ). Such rings aren't domains: both and are nonzero in , yet their product (which is ) is zero in . To wit, in yet in .
An element is said to be invertible or a unit if there exists with . The set of all units is the group of units of is the set of all units of . It is a group under multiplication, and is sometimes written , or even . For instance
Two elements and in a ring are said to be associates if they are the same up to a unit in the sense that there is some unit such that .
A field is a ring in which every nonzero element has an inverse. Typical examples include the rational numbers , the real numbers and the complex numbers . There are also the prime fields for a (rational) prime (for instance encountered above) and more generally, the finite fields of size where is a prime power. Number fields discussed in this text are fields (by definition).
There are of course exceptions, and many classical results determining the structure of groups of units of rings.
For rings of the form it is enough, thanks to the Chinese Remainder Theorem to deal with the prime power case :
It is a fact that finite subgroups of (for any field ) are cyclic. As a consequence:
If is any ring, its ring of polynomials, , then
In particular, if is reduced then .
Likely the most important example on this list is the (noncommutative) ring of matrixes for a (commutative) ring : its units are precisely those matrices whose determinant is a unit in .
where is the product of two large primes. ↩︎
computing their order is equivalent to factoring , and is a difficult problem ↩︎
to generate two large primes , their product and be trusted with discarding the factors and . ↩︎
of Imaginary Quadratic Number Fields , ↩︎
of quadratic number fields ↩︎
discrete, spanning subgroups . ↩︎
and lattice methods play a significant role in ANT. ↩︎
no relation with the order a group introduced earlier. ↩︎
and which is invariably discussed in pretty much every other text on the subject ↩︎
according to Wolfram Alpha, does the job. ↩︎
isomorphic ↩︎
That should be an isomorphism rather than an equality. ↩︎
The units of a ring are its invertible elements, i.e. those elements such that there exists with . The units of are and . ↩︎
existence of factorizations, that is ↩︎
existence of factorizations, that is ↩︎
In the same sense as before: up to reordering and up to units. ↩︎
(without proof) ↩︎
This requires a computation which we skip. ↩︎
It is a simple task to verify that these are indeed ideals. ↩︎
i.e. the are noetherian. Dedekind rings are noetherian by definition. ↩︎
Prime ideals are usually defined as the ideals of such that the quotient ring is a domain. ↩︎
and Dedekind domains more generally. ↩︎
Domains with only principal ideals are called Principal Ideal Domains (PID). ↩︎
The proof in Baker is surprisingly simple yet quite non-trivial. ↩︎
We stole that sentence from A Conversational Introduction to Algebraic Number Theory by ↩︎
using the standard characterization of prime ideals as those ideals whose quotient ring is a domain. ↩︎
and more generally any Dedekind domain ↩︎
euclidean, actually ↩︎
and we already explained why back then ↩︎
of either elements or ideals ↩︎
for all , ↩︎
Conventions vary. ↩︎
if we consider for instance all -rational points. ↩︎
so is invertible with inverse , so is invertible with inverse , so is invertible and is its own inverse. ↩︎
so is invertible and is its own inverse, so is invertible and is its own inverse, so is invertible and is its own inverse ↩︎