Table des mati` eres
XV
6.7
Appendice : le produit scalaire et les corps finis . . . . . . . . . . . . . . . . . . . . 203
6.8
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7 La cryptographie ` a cl´ e publique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.2
Quelques outils de th´ eorie des nombres . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
7.3
Le principe du code RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
7.4
Construire de grands nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
7.5
L’algorithme de Shor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.6
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
8 G´ en´ erateurs de nombres al´ eatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.2
Le registre `
a d´ ecalage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
8.3
G´ en´ erateurs F p -lin´ eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
8.3.1 Le cas p = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
8.3.2 Une le¸ con pour les jeux de hasard . . . . . . . . . . . . . . . . . . . . . . . . . . 259
8.3.3 Le cas g´ en´ eral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
8.4
G´ en´ erateur r´ ecursif multiple combin´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
8.5
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
8.6
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
9 Google et l’algorithme PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
9.1
Les moteurs de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
9.2
Toile et chaˆ ınes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
9.3
PageRank am´ elior´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
9.4
Le th´ eor` eme de Frobenius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
9.5
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
10 Pourquoi 44 100 nombres ` a la seconde ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
10.2 La gamme musicale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
10.3 La derni` ere note (introduction `
a l’analyse de Fourier) . . . . . . . . . . . . . . . 304
10.4 La fr´ equence de Nyquist et le pourquoi du 44 100 . . . . . . . . . . . . . . . . . . 315
10.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
XV
6.7
Appendice : le produit scalaire et les corps finis . . . . . . . . . . . . . . . . . . . . 203
6.8
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7 La cryptographie ` a cl´ e publique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.2
Quelques outils de th´ eorie des nombres . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
7.3
Le principe du code RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
7.4
Construire de grands nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
7.5
L’algorithme de Shor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.6
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
8 G´ en´ erateurs de nombres al´ eatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.2
Le registre `
a d´ ecalage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
8.3
G´ en´ erateurs F p -lin´ eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
8.3.1 Le cas p = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
8.3.2 Une le¸ con pour les jeux de hasard . . . . . . . . . . . . . . . . . . . . . . . . . . 259
8.3.3 Le cas g´ en´ eral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
8.4
G´ en´ erateur r´ ecursif multiple combin´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
8.5
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
8.6
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
9 Google et l’algorithme PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
9.1
Les moteurs de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
9.2
Toile et chaˆ ınes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
9.3
PageRank am´ elior´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
9.4
Le th´ eor` eme de Frobenius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
9.5
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
10 Pourquoi 44 100 nombres ` a la seconde ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
10.2 La gamme musicale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
10.3 La derni` ere note (introduction `
a l’analyse de Fourier) . . . . . . . . . . . . . . . 304
10.4 La fr´ equence de Nyquist et le pourquoi du 44 100 . . . . . . . . . . . . . . . . . . 315
10.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325