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
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.
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.
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.
Cryptographie: une introduction élémentaire ppt 3,4 Mo, 90 p. print pdf 3,3 Mo, 23 p.
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.
Le test de Rabin-Miller.
Le test de Pocklington-Lehmer.
L'algorithme AKS (polynomial).
L'algorithme ECPP (basé sur les courbes elliptiques).
- 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)
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)
.
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.
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.).