Miller-Rabin, nombres de Carmichael
dans Arithmétique
Le Test de Miller Rabin est un test déterministe de primalité d'un entier $n$ dans le sens ou il teste, pour un grand nombre d'entiers $a$, le petit théorème de Fermat (en fait sa contraposée):
si $a^{n-1} \neq 1 mod n$ alors $n$ est composé.
Cependant, il existe des nombres dits de Carmichael, qui échappent à ce test (ils vérifient la congruence du th. de Fermat, bien qu'ils ne soient pas premiers).
Or, les textes disent que pour un entier $a$ choisi au hasard pour le test ci-dessus, il y a une probabilité inférieure à 1/4, donc si on effectue $p$ tests successifs, on retourne le résultat "n est probablement premier", avec une probabilité d'erreur inférieure à $(1/4)^p$.
Ma question est: comment établit-on ce genre de résultat concernant la répartition des nombres de Carmichael, quels résultats de théorie des nombres sont utilisés ?
Merci d'avance, hugo.
si $a^{n-1} \neq 1 mod n$ alors $n$ est composé.
Cependant, il existe des nombres dits de Carmichael, qui échappent à ce test (ils vérifient la congruence du th. de Fermat, bien qu'ils ne soient pas premiers).
Or, les textes disent que pour un entier $a$ choisi au hasard pour le test ci-dessus, il y a une probabilité inférieure à 1/4, donc si on effectue $p$ tests successifs, on retourne le résultat "n est probablement premier", avec une probabilité d'erreur inférieure à $(1/4)^p$.
Ma question est: comment établit-on ce genre de résultat concernant la répartition des nombres de Carmichael, quels résultats de théorie des nombres sont utilisés ?
Merci d'avance, hugo.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Dans Gourdon algèbre (pb 2 ,p35) : plusieurs résultats qui peuvent t'intéresser
<BR>
<BR>Plus généralement, les articles d'Andrew Granville sont à lire et/ou à redécouvrir, car le bonhomme est très clair.
<BR>
<BR>Borde.<BR>
<BR>[Lien réparé. AD]
<BR>
<BR>Borde.<BR>