Petit théorème de Fermat : pourquoi 341 trompe le test

Intervenant 10:00

Bienvenue à l'écoute de cette exploration sur le podcast du magazine Tangente. D'habitude, quand on cherche à vérifier une vérité scientifique, on s'attend à une réponse binaire. C'est vrai ou c'est faux ?

Intervenant 20:13

Ben oui, on veut que ce soit clair, quoi.

Intervenant 10:15

C'est ça. L'interrupteur, il est soit allumé, soit éteint.

Intervenant 20:19

Et c'est une clarté qu'on recherche particulièrement en sciences exactes, en fait.

Intervenant 10:23

Sauf que, quand on plonge dans la théorie des nombres, et plus particulièrement dans la traque des nombres premiers, cet interrupteur a parfois, disons, d'étranges faux contacts.

Intervenant 20:34

C'est le paradoxe fascinant qu'on explore aujourd'hui.

Intervenant 10:37

Exactement. Et on se base sur un super article intitulé « pratique du petit théorème ». Notre mission aujourd'hui, c'est de décrypter les méthodes mathématiques qui permettent de vérifier si un nombre est réellement premier. Et on va voir pourquoi, de façon assez contre-intuitive, la méthode la plus simple n'est pas toujours celle qui offre une certitude absolue.

Intervenant 20:58

Alors, le point de départ de cette quête, il s'appuie sur le petit théorème de Fermat. En gros, plutôt que d'essayer de diviser un nombre immense par tous les nombres précédents, ce qui prendrait un temps infini, on lui fait subir une sorte de test d'effort.

Intervenant 11:11

Un crash-test un peu.

Intervenant 21:12

Voilà, c'est ça. On prend un nombre au hasard, on teste si sa puissance P-1 est égale à 1, modulo P, et si la théorie tient la route et que le reste de la division n'est pas strictement égal à 1, notre candidat est définitivement un imposteur, il n'est pas premier.

Intervenant 11:28

Donc il est recalé d'office.

Intervenant 21:30

Directement. Et l'avantage, c'est qu'informatiquement, ce petit test est une rapidité redoutable.

Intervenant 11:36

Bon, décortiquons tout ça. Si on suit cette logique, ce test d'effort, il agit un peu comme un physionomiste de boîte de nuit très expéditif, tu vois.

Intervenant 21:45

Ah, j'aime bien cette analogie !

Intervenant 11:47

Il jette un coup d'œil très rapide à un détail de la carte d'identité. Ça lui permet d'analyser un flux massif de candidats à une vitesse folle. Sauf que fatalement, ce physionomiste a une faille. Il se laisse parfois berner par de fausses cartes d'identité.

Intervenant 22:00

Des contrefaçons très spécifiques. L'article mentionne d'ailleurs l'exemple précis du nombre 341. 341 passe ce test d'effort haut la main. Sous cet angle précis, il a le masque parfait d'un nombre premier alors qu'en fait c'est le produit de 11 par 31.

Intervenant 12:18

D'accord, donc c'est un faux positif.

Intervenant 22:20

C'est le problème, ouais. Mais pour pallier cette faille, les mathématiciens Michael Rabin, qui est né en 1931, et Gary Miller, né en 1948, ont proposé une évolution majeure. Au lieu que le physionomiste vérifie un seul détail au hasard, on va le forcer à vérifier une multitude de critères différents, pour un certain nombre de valeurs qu'on appelle K.

Intervenant 12:43

Donc on multiplie les contrôles.

Intervenant 22:45

Exactement. En multipliant ces tests indépendants, le risque qu'un imposteur ait le masque parfait à chaque fois s'effondre. La probabilité d'erreur chute drastiquement à 1 sur 4 à la puissance k.

Intervenant 12:58

Ah oui, ce qui devient très vite négligeable en fait.

Intervenant 23:00

Ah bah totalement. Pour donner un ordre d'idée tiré du texte, pour des nombres inférieurs à 25 milliards, la probabilité d'erreur n'est que d'environ 2 fois 10 puissance moins 5.

Intervenant 13:10

C'est microscopique.

Intervenant 23:11

Vraiment.

Intervenant 13:12

Mais, et c'est là que ça devient intéressant, voilà où ça coince d'un point de vue purement logique. Ça reste de la probabilité. Comment est-ce qu'on fait pour passer de cette très forte probabilité à une certitude absolue sans que le calcul ne prenne des années ?

Intervenant 23:29

Et bien c'est justement cette quête du déterminisme pur qui a mené à une percée majeure en août 2002.

Intervenant 13:35

D'accord.

Intervenant 23:36

Trois chercheurs indiens, Manidra Agrawal, Neeraj Kayal et Nitin Saxena, ont publié le test AKS.

Intervenant 13:45

Le fameux test AKS ?

Intervenant 23:47

Voilà, et contrairement à Miller-Habin, AKS est purement déterministe. Ils utilisent une formule rigoureuse. En gros, grand X moins petit a, le tout à la puissance p, égale grand X à la puissance p moins petit a modulo p.

Intervenant 14:01

Oulah, attends. Le problème, c'est que évaluer tous les coefficients de ce polynôme, ça demande un temps absolument prohibitif. C'est comme devoir compter chaque grain de sable d'une plage.

Intervenant 24:11

C'est vrai, les ordinateurs satureraient complètement. Mais c'est là qu'intervient leur astuce géniale.

Intervenant 14:18

Pour

Intervenant 24:18

rendre le test effectif, ils évaluent l'identité modulo un autre polynôme, x puissance r moins 1.

Intervenant 14:25

Ok, donc ce modulo il agit un peu comme une boîte rigide qui va limiter la taille du problème.

Intervenant 24:30

C'est ça. Pour des valeurs de R convenables et un certain nombre de valeurs de A, on sait avec une certitude déterministe si P est premier.

Intervenant 14:38

C'est fascinant. Ça nous laisse une vraie dualité en fait. On a le choix entre un test probabiliste ultra rapide, comme Miller-Rabbin, et ce test déterministe infaillible, KAKS. Ce

Intervenant 24:49

qui m'amène à une réflexion finale assez provocatrice d'ailleurs.

Intervenant 14:53

Je t'écoute.

Intervenant 24:54

Si l'approche probabiliste était déjà suffisamment fiable pour l'immense majorité des cas pratiques, avec des risques d'erreurs

Intervenant 14:59

infimes d'exploration, et à très bientôt.