Si un de ces N tests retourne la valeur faux alors p n'est pas premier.
D'ailleurs, en pratique, dès le premier échec, on arrête le test car on est certain que le nombre testé n'est pas premier (cf. ce que tu mets sur l'implication et la logique)
... par le fait que le théorème de Fermat est une implacation ...
En toute rigueur, il s'agit du petit théorème de Fermat.
Mais la réciproque est fausse. En revanche on peut prouver que la proposition p est premier est vraie avec une certaine probabilité.
FAUX (sauf en logique flou et d'une manère plus générale avec les logiques pour lesquelles les valeurs possibles d'un théorème ne sont pas que vrai ou faux - logiques dites multimodales mais je ne suis pas certain du terme)
Dans le cas de Miller-Rabin (voir http://www.security-labs.org/index.php3?page=5(...)) on part de l'hypothèse qu'un entier n impair est fortement pseudo-premier par rapport à b pour au plus 25% des nombres b (0<b<n). Cela signifie que si n et b ne sont pas fortement pseudo-premiers, alors n n'est pas premier.
Ainsi, pour chaque b testé, on a une probabilité de 0.25 que n soit composite. Si on répète le test p fois, la probabilité que n soit composite descend alors à 0.25^p
Bref, tout cela pour dire que les tests probabilistes donnent comme information une probabilité pour qu'un nombre soit composite.
[^] # Re: Compléments
Posté par pappy . En réponse à la dépêche Encore plus de Nombres Premiers. Évalué à 10.
D'ailleurs, en pratique, dès le premier échec, on arrête le test car on est certain que le nombre testé n'est pas premier (cf. ce que tu mets sur l'implication et la logique)
... par le fait que le théorème de Fermat est une implacation ...
En toute rigueur, il s'agit du petit théorème de Fermat.
Mais la réciproque est fausse. En revanche on peut prouver que la proposition p est premier est vraie avec une certaine probabilité.
FAUX (sauf en logique flou et d'une manère plus générale avec les logiques pour lesquelles les valeurs possibles d'un théorème ne sont pas que vrai ou faux - logiques dites multimodales mais je ne suis pas certain du terme)
Dans le cas de Miller-Rabin (voir http://www.security-labs.org/index.php3?page=5(...)) on part de l'hypothèse qu'un entier n impair est fortement pseudo-premier par rapport à b pour au plus 25% des nombres b (0<b<n). Cela signifie que si n et b ne sont pas fortement pseudo-premiers, alors n n'est pas premier.
Ainsi, pour chaque b testé, on a une probabilité de 0.25 que n soit composite. Si on répète le test p fois, la probabilité que n soit composite descend alors à 0.25^p
Bref, tout cela pour dire que les tests probabilistes donnent comme information une probabilité pour qu'un nombre soit composite.