Pourquoi Miller-Rabin au lieu du test de primalité de Fermat?

D'après la preuve de Miller-Rabin , si un nombre passe le test de primalité de Fermat , il doit également passer le test de Miller-Rabin avec la même base (une variable dans la preuve). Et la complexité du calcul est la même.$a$

Ce qui suit est tiré du test de primalité de Fermat :

Alors que les nombres de Carmichael sont sensiblement plus rares que les nombres premiers, 1 il y en a suffisamment pour que le test de primalité de Fermat ne soit souvent pas utilisé sous la forme ci-dessus. Au lieu de cela, d' autres extensions plus puissantes du test de Fermat, telles que Baillie-PSW, Miller-Rabin et Solovay-Strassen sont plus couramment utilisées.

Quel est l'avantage de Miller-Rabin et pourquoi il serait plus puissant que le test de primalité de Fermat?

L'algorithme de Rabin-Miller teste également, étant donné un nombre , si Z n a une racine non triviale d'Unity.$n$$Z_n$

Numéros Carmichael passent le test Fermat (pour chaque base ), mais pour chaque nombre Carmichael n , il existe de nombreux numéros un tel que le test pour les racines de l' unité échoue sur un (qui est, la séquence a , 2 a , . . . , 2 r a montre finalement une racine d'unité non triviale).$a$$n$$a$$a$$a,2a,...,2^ra$

Ainsi, nous avons les éléments suivants:

Pour le test de Fermat, si un nombre composé est pas Carmichael, alors la probabilité que le test permet de détecter compositeness est d' au moins 1 / deux . Cependant, le test échouera à tous les numéros de Carmichael.$n$$1/2$

Pour le test Rabin-Miller, chaque numéro composite sera détecté avec une probabilité d' au moins . Cela signifie que la probabilité de correction est indépendante de l'entrée (il n'y a pas d'entrées "dures"). C'est ce qui rend cet algorithme plus fort.$1/2$

Je pense que votre déclaration est à l'opposé de ce qui se passe. Passer le test de Miller-Rabin pour une base donnée signifie qu'il passera le test de Fermat pour la même base. En revanche, il existe de nombreux composites qui passeront le test de Fermat pour une base donnée mais échoueront au test de Miller-Rabin pour la même base.

Voir, par exemple, l'article de Pomerance / Selfridge / Wagstaff sur la page Wikipedia Miller-Rabin:

https://math.dartmouth.edu/~carlp/PDF/paper25.pdf

où nous voyons un diagramme à la page 2 montrant les pseudoprimes d'Euler étant un sous-ensemble des pseudoprimes de Fermat, et les pseudoprimes forts étant un sous-ensemble de ceux-ci. Le test de Solovay-Strassen est donc plus clairvoyant que le test de Fermat, et le test de Miller-Rabin plus que l'un ou l'autre. Ils évitent tous les deux le problème critique des nombres de Carmichael. Ils ont essentiellement les mêmes performances, nous préférons donc utiliser le test de Miller-Rabin.

Il devrait être évident que Miller-Rabin est meilleur que Fermat.

Avec le test de Fermat, on vérifie si = 1 (modulo p).$a^{p-1}$

$a^{p-1}$$p-1 = s·2^k$$a^s$$a^{p-1}$

Encore une fois, si le résultat n'est pas 1 (modulo p) alors p est composite. Mais si le résultat est 1 modulo p, alors nous vérifions si nous avons obtenu ce 1 en mettant au carré un résultat intermédiaire qui n'était pas +1 ou -1, et dans ce cas, x est également un composite prouvé.

Nous faisons donc exactement la même quantité de travail, mais il existe d'autres moyens de prouver que x est composite.