Algebraic Structures, Cryptography, Number Theory and Applications

Praia, Santiago, Cape Verde

April, 13th to 28th, 2015

All the courses are given in 8 lectures and feature a tutorials session

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; howerer 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.

In this course, we will deal with 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.

Examples of elliptic curves, drawing elliptic curves, the set of rational points of an elliptic curve, intersection between 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.

The purpose of this course is to provide an approach to primality, through the known tests and / or criteria of primality: Fermat; Miller-Rabin; Solovay Strassen; Pepin-; Lucas-Lehmer. RSA encryption system is given as an application. We also look, to the problem of to the completion's duration of these tests, including giving the test algorithms primality's Agrawal-Kayal-Saxena [AKS], which is in polynomial time. We also point out the difficulty of the prime factorization using the example of the algorithm of Pollard. To reach these objectives, We Will make a brief Recalls of arithmetic in Z: The multiplicative functions, distribution of primes, primitive roots modulo p, the Legendre symbol (Theorem Terjanian-Fermat), developments continued fractions (Pell equations, application to non primality of Fermat's numbers considered as a sum of squares). In particular, we will focus on solving: Systems of congruencies, Polynomial equations of congruencies (with an application to the Great Fermat's theorem), and Hensel's Lemma