# CIMPA Research School "Cryptography, theoretical and computational aspects of algebraic number theory and algebra", Haiti 2019

Nov 4 – 15, 2019
Institut des sciences, des technologies et des études avancées d'Haiti, Cap Haïtien
America/Port-au-Prince timezone

## List of courses

The school will host the following courses:

• Some aspects of algebraic number theory related with cryptography
by Michel Waldschmidt (University Paris 6, France)
Abstract
• Elementary number theory and cryptography
by Alain Togbé (Purdue University Northwest, USA) and Jean-Marie Vilaire (ISTEAH, Haiti)
Abstract
• Elementary Approach to Elliptic Curves
by Francesco Pappalardi (Università Roma Tre, Italy)
Abstract
• On prime numbers and primality tests
by Carlos Gustavo Moreira (IMPA, Brazil)
Abstract
• Representations of the Symmetric Group and Applications
by Alfred Noel (University of Massachusetts Boston, USA)
Abstract
• Introduction to Algorithmic Number Theory
by Cécile Armana (University of Franche-Comté, France)
Abstract
• Lattices and Cryptography
by Adriana Salerno (Bates College, USA)
Abstract

Abstracts

Some aspects of algebraic number theory related with cryptography (Michel Waldschmidt, 6 hours)

This course will introduce some of the main basic tools from number theory which are essential for the modern cryptographic systems. Starting with the arithmetic of rational integers, divisibility and congruences will be explained in connection with algebra (group theory, especially cyclic groups; rings, ideals, quotients; fields). The finite fields with a number of elements which is a prime number occur naturally in this context; however they do not suffice for advanced purposes, and the general theory of finite fields will be developed. Such a theory has a lot of deep applications, some of which will be outlined.

Elementary number theory and cryptography (Alain Togbé and Jean-Marie Vilaire, 7 hours)

In this course, we will introduce the basics of the elementary number theory to introduce cryptography. So we will use the theory of congruences to gently introduce cryptography. We will start from the Caesar cipher to present the public-key cryptography. We will also discuss the knapsack cryptosystem (which is based on the difficult classic problem in combinatorics known as the knapsack problem) and the discrete logarithm problem.

Elementary Approach to Elliptic Curves (Francesco Pappalardi, 6 hours)

Examples of elliptic curves, drawing elliptic curves, the set of rational points of an elliptic curve, intersection of a line and an elliptic curve, the point at infinity of an elliptic curve, basics of projective geometry, singular points, the group law, Weierstrass equations and their classification, elliptic curves over finite fields and their properties, the Hasse bound, the structure of the group of points over finite fields, applications to cryptography.

On prime numbers and primality tests (Carlos Gustavo Moreira, 6 hours)

On prime numbers and primality tests including probabilistic tests, the Agrawal-Kayal-Saxena test and tests for particular families of numbers, as Pepin, Pocklington and the Lucas-Lehmer test for Mersenne numbers, and a discussion on recurrent sequences and primality tests.

Representations of the Symmetric Group and Applications (Alfred Noel, 6 hours)

This course is an introduction the Representation Theory of the finite symmetric group with a view toward real world applications. Due to time constraint we will only cover the following: G-modules and the Group Algebra, Complete Reducibility and Maschke's Theorem, Group Characters, Young Tableaux and Tabloids, Specht Modules, Standard Tableaux and a basis for Specht Modules, The Hook formula, Applications to Multi-object tracking using Fourier analysis on finite groups.

Introduction to Algorithmic Number Theory (Cécile Armana, 6 hours)

In number theory, several problems can be studied from the viewpoint of explicit computations and algorithms. This allows to compute important objects and produce numerical experiments which are often useful: numerical checks for conjectures, description of examples and counterexamples, gain in intuition. In this course we will start with classical algorithms and their analysis (Horner method for evaluating polynomials, modular arithmetic, Euclidean algorithms, exponentiation by squaring,...). We will then focus on algorithms more specific to number theory (squares modulo a prime number, (pseudo)-primality tests). If time allows, we will discuss more advanced algorithms based on elliptic curves (Schoof's algorithm for counting points on elliptic curves over finite fields, Lenstra's factorization algorithm of integers, elliptic curve primality tests).

Lattices and Cryptography (Adriana Salerno, 6 hours)

Review on vector spaces and lattices. The shortest vector problem and the closest vector problem. Babai's algorithm for finding "good" bases. Cryptosystems based on hard lattice problems: The GGH Public Key Cryptosystem, The NTRU Public Key Cryptosystem. Possible additional topics: Lattice-based digital signature schemes. Lattice reduction algorithms. Fully homomorphic encryption.