Class-groups – USF Crypto

Ideal Class Groups

This mini-course introduces some techniques of class group computations that are relevant to isogeny-based cryptography. It is a part of the Bristol 2021 summer school on isogeny based cryptography. Each short video comes with a PDF with lecture notes. We recommend using them while viewing the videos. Together with the module, we put together a Sage worksheet hosted via CoCalc during the time of the course. It follows the elementary steps of the computation of a class group and of decomposing ideals according to a set of generators for a toy example. The worksheet is accessible using the link below:

Introduction to Number Fields

Module One

Learning Objectives:

a) The students will be able to construct quadratic number fields and cyclotomic numbers fields.

b) The students will be able to calculate algebraic norms.

c) The students will be able to calculate traces.

d) The students will be able to calculate the discriminant of an order.

Lecture Notes PDF

Ideals in Number Fields

Module Two

Learning Objectives:

a) The students will be able to perform arithmetic operations on ideals.

b) The students will be able to distinguish split/inert/ramified primes.

c) The students will be able to construct prime ideals for primes not dividing the index.

d) The students will be able to calculate the norm of an ideal.

Lecture Notes PDF

Ideal Class Groups

Module Three

Learning Objectives:

a) The students will be able to identify prime generators of the class group, unconditionally and conditionally to GRH

b) The students will be able to identify the structure of the unit group from the signature of the field.

c) The students will be able to derive an estimate for the product regulator*class number.

Lecture Notes PDF

Quadratic Number Fields

Module Four

Learning Objectives

a) The students will be able to construct quadratic orders from their discriminant.

b) The students will be able to construct fractional ideals in quadratic orders.

c) The students will be able to identify split/ramified/inert primes in quadratic orders.

d) The student will be able to identify units in imaginary quadratic orders.

e) The students will be able to map ideals to quadratic forms.

Lecture Notes PDF

The Cayley Graph of the Class Group

Module Five

Learning Objectives:

a) The students will be able to draw the Cayley graph of a group.

b) The students will be able to rephrase ideal decomposition in the class group in terms of walks in the Cayley graph.

c) The students will be able to identify the spectral properties of the Clayley graph that lead to rapid mixing of random walks.

Lecture Notes PDF

The Hafner-McCurley Algorithm

Module Six

Learning Objectives:

a) The students will be able to specify the relationship between the subexponential complexity and polynomial/exponential complexities.

b) The students will be able to identify the two main steps steps of subexponential class group computation.

c) The students will be able to derive relations between generators of the class group.

Lecture Notes PDF

Applications of Class Group Computation

Module Seven

Learning Objectives:

a) The students will know how to decompose an input ideal on a small set of generators of the class group.

b) The students will know how to produce short decompositions of ideals.

c) The students will know how to compute the class group of a suborder from the class group of the maximal order.

Lecture Notes PDF

Class Groups of Large Degree Number Fields

Module Eight

Learning Objectives:

a) The students will be able to reduce an ideal with the BKZ lattice reduction technique.

b) The students will be able to use ideal reduction to produce relations between generators of the class group.

c) The students will be able to identify the main heuristics required to mimic Hafner and McCurley's method in large degree.

Lecture Notes PDF