Suivi de l'École de recherche CIMPA
Théorie des Nombres et Algorithmique
qui s'est tenue à la
Faculté des Sciences et Techniques (FAST) de l'Université de Bamako (Mali)
du 15 au 26 novembre 2010.


    Site local de l'école de recherche:
        http://www.ml.refer.org/ecole-cimpa-bko2010/index.html
    Page du site du CIMPA dédiée à l'école de recherche:
        http://www.cimpa-icpam.org/spip.php?article236
    Rapport (en français) sur l'école de recherche:
       http://www.math.jussieu.fr/~miw/articles/pdf/CimpaBamako2010.pdf
    Messages de remerciements:
       http://www.cimpa-icpam.org/IMG/pdf/Mel_Remerciements.pdf
    Adresse URL de cette page:
       http://www.math.jussieu.fr/~miw/BamakoCIMPA2010.html

Liste des cours

    Fondements de l'arithmétique, Yann Bugeaud, Strasbourg.
    Arithmétique des grands entiers, Maurice Mignotte, Strasbourg.
    Introduction élémentaire à la cryptographie, Michel Waldschmidt, Paris.
    Équations de Pell-Fermat, Michel Waldschmidt, Paris.
    Tests de primalité, Maurice Mignotte, Strasbourg.
    Algorithmes de factorisation, Francesco Pappalardi, Rome.
    Suites récurrentes linéaires, Pietro Corvaja, Udine.
    Formes quadratiques, Jorge Jimenez, Madrid.
    Initiation au système de calcul pari-gp et illustrations concrètes des cours, Christophe Delaunay, Lyon.
    Séances de tutorats, Francesco Pappalardi, Rome.
    Atelier sur l'accès à la documentation mathématique par internet, Anders Wandahl, Stockholm.

Fondements de l'arithmétique, Yann Bugeaud, Strasbourg

    Algorithme d'Euclide-Bezout.
    Théorème chinois,
    Équations diophantiennes linéaires,
    Z/nZ
    Polynomes
    Introduction aux fractions continues
Référence :
    Y. Bugeaud.- Notes de cours sur les fractions continues.

Arithmétique des grands entiers, Maurice Mignotte, Strasbourg

Les grands entiers apparaissent en particulier en cryptographie (méthode RSA, logarithme discret, cryptographie elliptique, ...) et dans la résolution de certaines équations diophantiennes (c'est par exemple le cas quand on utilise la méthode de Baker). On se limitera à considérer la question du codage de ces entiers et à l'étude des opérations de base : addition, soustraction, multiplication et division, ainsi que l'exponentiation rapide. Pour chacune de ces opérations, on s'intéressera avant tout à l'aspect pratique, mais il sera aussi question des problèmes théoriques de complexité. Il s'agit d'un cours très élémentaire.
Références :
    Algorithmic Number Theory: Lattices, Number Fields, Curves and cryptography .- ed. J. P. Buhler, P. Stevenhagen, Cambridge University Press, 2008.
    A. V. Aho, J. E. Hopcroft, J. D. Ullman .- The Design and Analysis of Computer Algorithms, Add. Wesley, 1974.
    H. Cohen .- A course in computational algebraic number theory, Graduate Texts in Mathematics 138, Springer, Berlin, 1993.
    J. von zur Gathen and J. Gerhard .- Modern Computer Algebra, Cambridge, 2003.
    D. Knuth .- The art of programming, II: seminumerical algorithms, 2nd ed., Addison Wesley, Reading, Ma., 1981.
    M. Mignotte .- Mathématiques pour le Calcul Formel, PUF, Paris, 1989.
    Arbitrary precision arithmetic
    Implementing multiple precision arithmetic.
    M. Mignotte .- Notes de cours.
    M. Mignotte .- Notes de cours sur les polynômes.

Introduction élémentaire à la cryptographie, Michel Waldschmidt, Paris

Cryptographie: une introduction élémentaire   ppt 3,4 Mo, 90 p.   print pdf 3,3 Mo, 23 p.

Équations de Pell-Fermat, Michel Waldschmidt, Paris

1. Historique
        1.1 Le troupeau d'Archimède
        1.2 Brahmagupta, Bhaskara II, Narayana (cf.[W])
        1.3. Pell, Fermat, Brounckner, Euler, Lagrange
2. Fractions continues
        2.1 Théorie générale (cf. [Bo], [Bo-vdP])
        2.2 Propriétés spécifiques du développement de la racine d'un entier positif non carré
        2.3 Taille des solutions (cf.[Z])
3. Algorithme pour résoudre l'équation
        TD: faire des calculs sur ordinateur, établir des tables, comparer les estimations de la solution fondamentale avec la théorie
4. Unités d'un corps de nombres: théorème de Dirichlet. Géométrie des nombres.
5. Applications:
        Sur la topologie de certains espaces provenant de constructions arithmétiques (cf. [Be])
        Substitutions de mots de Christoffel (cf. [B-L])
        Quadrature du carré (cf. [S]).
[Be] N. Bergeron, Sur la forme de certains espaces provenant de constructions arithmétiques, Images des Mathématiques, (2004).
[Bo] E. Bombieri, Continued fractions and the Markoff tree, Expo. Math., 25 (2007), pp. 187-213.
[Bo-vdP] E. Bombieri and A.J. van der Poorten, Continued fractions of algebraic numbers, in Computational algebra and number theory Sydney, 1992, vol.325 of Math. Appl., Kluwer Acad. Publ., Dordrecht, 1995, 137-152.
[B-L] J.-P. Borel and F.Laubie, Quelques mots sur la droite projective réelle, J. Th\'eor. Nombres Bordeaux, 5 (1993), 23--51.
[S] M.R. Schroeder, Number theory in science and communication, With applications in cryptography, physics, digital information, computing, and self-similarity. vol. 7 of Springer Series in Information Sciences, Springer-Verlag, Berlin, fourth ed., 2006.
[W] A. Weil, Number theory, An approach through history from Hammurapi to Legendre, Reprint of the 1984 edition. Modern Birkhäuser Classics, Birkhäuser Boston Inc., Boston, MA, 2007.
[Z] D. Zagier, On the number of Markoff numbers below a given bound, Math. Comp., 39 (1982), 709-723

Premier cours: présentation beamer sur L'équation dite de Pell-Fermat x^2-dy^2=\pm 1
            version écran: 2 Mo, 86 (197) p.   version pour imprimer: 1.1 Mo, 22 p.
Les cours suivants ont été donnés en français (comme tous les cours de cette école), bien que la rédaction soit en anglais:
Notes du cours:
            L'équation de Pell-Fermat (55 p., 434 Ko).
Contents
    1 On the so–called Pell–Fermat equation. Examples of simple continued fractions. Existence of integer solutions. All integer solutions. On the group of units of Z[\sqrt{D}]. Connection with rational approximation.
    2 Continued fractions. Generalized continued fractions. Simple continued fractions. Finite simple continued fraction of a rational number. Infinite simple continued fraction of an irrational number.
    3 Continued fractions and Pell’s Equation. The main lemma. Simple Continued fraction of \sqrt{D}. Connection between the two formulae for the n-th positive solution to Pell’s equation. Records. Periodic continued fractions. Diophantine approximation and simple continued fractions. A criterion for the existence of a solution to the negative Pell equation. Arithmetic varieties.
    4 More on Diophantine Approximation. Irrationality Criterion. Liouville’s inequality.

Tests de primalité, Maurice Mignotte, Strasbourg

    Le test de Rabin-Miller.
    Le test de Pocklington-Lehmer.
    L'algorithme AKS (polynomial).
    L'algorithme ECPP (basé sur les courbes elliptiques).

Algorithmes de factorisation, Francesco Pappalardi, Rome

    - Méthode ro de Pollard
    - Méthode p-1 de Pollard
    - Méthode ECM de Lenstra (basée sur les courbes elliptiques)
    - Méthode du crible quadratique (QS)
    - Méthode du crible algébrique sur les corps de nombres (NFS)

Suites récurrentes linéaires, Pietro Corvaja, Udine

    1) Définition, représentation des suites récurrentes linéaires comme polynômes exponentiels
    2) Motivations: fonctions rationnelles, itérations d'automorphismes linéaires (puissances de matrices carrées), relations avec l'équation de Pell-Fermat, nombre de points rationnels d'une courbe sur un corps fini
    3) Le théorème de Skolem-Mahler-Lech
    4) Problèmes diophantiens: équations algébriques avec suites récurrentes linéaires; questions de divisibilité; pgcd(a^n-1, b^n-1)
    5) Applications: ordre modulo N d'une matrice à coefficients entiers (avec applications aux courbes elliptiques sur les corps finis) .

Formes quadratiques, Jorge Jimenez, Madrid

    1. Forms $x^2+dy^2 for d=-1,1,2$ Appendix. Quadratic reciprocity law
    2. Quatratic forms. Basic facts. The purpose is to study when a form represents properly an integer $m$.
    3. Reduction of forms. Examples.
    4. Primes of the form $x^2+ny^2$ given by congruences. Automorphisms of a form.
    5. Genus.
    6. Composition.
    The purpose is to study representation of integers by binary quadratic forms. We will give some examples of forms $x^2+ny^2$ representing primes in certain congruences. Then, we will move into the basic theory of genus and composition.
Bibliography:
    Baker. A concise introduction to modern number theory
    Cox, Primes of the form $x^2+ny^2$.
    Gauss, Disquisitiones Arithmeticae,
    Ribenboim, My numbers my friends.
Fichiers à télécharger:
    Leçon 1     version écran 46 p.   version pour imprimer: 6 p.
    Leçon 2     version écran 36 p.   version pour imprimer: 7 p.
    Leçon 3     version écran 38 p.   version pour imprimer: 6 p.
   

Initiation au système de calcul pari-gp et illustrations concrètes des cours, Christophe Delaunay, Lyon

    1 - Prise en main du système pari-gp en l'utilisant pour illustrer les différentes notions du thème "Fondements de l'arithmétique".
    2 - Donner et faire des calculs sur des parties des cours (par exemple : créer un système RSA et montrer les pièges classiques - Regarder des tests de pseudo- primalité - ECPP - Méthode de Lenstra pour la factorisation - Faire "marcher" les algorithmes de résolution de l'équation de Pell-Fermat - etc.).  

Séances de tutorats, Francesco Pappalardi, Rome

Atelier sur l'accès à la documentation mathématique par internet, Anders Wandahl, Stockholm