Test de primalité qui découlerait du petit théorème de Fermat

invitea86f2934 · 27/04/2014, 19h47

Bonjour à tous !

Dans le cadre d'un projet, j'ai du travailler la preuve qui permet d'affirmer que le problème PRIME : "étant donné un entier n, ce dernier est-il premier ?" est un problème de classe P (via l'algorithme et le théorème AKS). J'aimerais montrer que si le petit théorème de Fermat avait caractérisé les nombres premiers (n premier ssi pour tout a entier $\text{[math]}$ ), alors on en aurait induit un algorithme polynomial quasi-directement... mais je ne le trouve pas (quels choix de a ?, etc.). Voilà en vous remerciant par avance de vos réponses !

invite57a1e779 · 27/04/2014, 19h57

Bonjour,

En testant tous les entiers de 2 à (n-1)/2, qu'est-ce que cela donne ?

invitea86f2934 · 27/04/2014, 20h21

Et bien justement je n'arrive pas à voir pourquoi un tel choix d'entiers a permettraient de conclure alors que la réciproque serait : si pour toutentier a on a que $\text{[math]}$ alors $\text{[math]}$ est premier...

invitea86f2934 · 27/04/2014, 20h28

PS : merci pour la rapidité de la réponse

A voir en vidéo sur Futura · Aujourd'hui

invite57a1e779 · 27/04/2014, 20h51

Je suppose que l'on commence par vérifier que n est impair...

1. La relation $\text{[math]}$ est satisfaite par $\text{[math]}$ et $\text{[math]}$ .

2. Si $\text{[math]}$ , alors : $\text{[math]}$ ( $\text{[math]}$ est impair), donc $\text{[math]}$ .

On vérifie la congruence pour les entiers de 2 à $\text{[math]}$ ; le point 1 l'étend aux entiers de 0 à $\text{[math]}$ et le point 2 l'étend encore aux entiers de $\text{[math]}$ à $\text{[math]}$ .

Comptons les biens cela fait $\text{[math]}$ entiers consécutifs ; comme on congrue modulo $\text{[math]}$ , on a le résultat pour tout entier $\text{[math]}$ .

invitea86f2934 · 27/04/2014, 22h37

D'accord merci beaucoup ^^ ne me reste alors plus qu'à montrer que tester ces entiers-là conduit à un test bien polynomial ! Encore merci de la vitesse et de la précision

Bonne soirée !

**Amanuensis** · 27/04/2014, 22h56

Sauf erreur de ma part, polynomial signifie dans le contexte polynomial en le logarithme de n.

L'algorithme évident (tester pour la division tous les entiers <= sqrt(n)) est en \sqrt(n), non polynomial et meilleur que le n/2 proposé!

invitea86f2934 · 27/04/2014, 23h28

Oui c'est bien ça ! Et c'est ce qui au final m'embête dans le cas présent : la plupart des articles sur le sujet (comme https://www-m3.ma.tum.de/foswiki/pub...aks_french.pdf) laissent supposer que, si les nombres de Carmichael n'existaient pas (les composés qui passent le "test de Fermat") alors l'algorithme qui en suivrait devrait être polynomial ! Et même en choisissant avec soin ces $\text{[math]}$ à tester je vois pas comment retomber sur une complexité en $\text{[math]}$

Test de primalité qui découlerait du petit théorème de Fermat

Test de primalité qui découlerait du petit théorème de Fermat

Re : Test de primalité qui découlerait du petit théorème de Fermat

Re : Test de primalité qui découlerait du petit théorème de Fermat

Re : Test de primalité qui découlerait du petit théorème de Fermat

Re : Test de primalité qui découlerait du petit théorème de Fermat

Re : Test de primalité qui découlerait du petit théorème de Fermat

Re : Test de primalité qui découlerait du petit théorème de Fermat

Re : Test de primalité qui découlerait du petit théorème de Fermat

Discussions similaires

petit théorème Fermat

petit théorème de fermat

Démonstration du petit théorème de Fermat

Petit théorème de Fermat

Petit théorème de Fermat