Tests probabilistes de primalité

Test de Fermat

Voici, pour a = 2, 3, 5, 7, 11, 13, la liste des puissances a n-1 (mod n) pour tous les entiers n composites impairs inférieurs à 215 et tels que 2n-1 = 1 (mod n), autrement dit les entiers pseudo-premiers pour la base 2.

Factorisation23571113
34111 * 31156675625367
5613 * 11 * 171375111541
6453 * 5 * 431365954361436
11055 * 13 * 171188511936
138719 * 7318751122112211411141
17297 * 13 * 191117421533
19053 * 5 * 127127640015612261846
204723 * 8911013622101311657
24655 * 17 * 29111480111
270137 * 73112554255425542554
28217 * 13 * 31111201612171
327729 * 113115672727110161016
403337 * 109134423442344224433442
436917 * 257133332024346943531735
43713 * 31 * 47132912257183422572257
468131 * 151145893783378312724589
546143 * 127113771137711621377
66017 * 23 * 41111377311
795773 * 109116802116211660582116
832153 * 157150365036150367209
84813 * 11 * 257180311024481964241783
89117 * 19 * 67111127411
1026131 * 3311102007131375271313721
105855 * 29 * 73114235111
113055 * 7 * 17 * 1911064183805796106411
128013 * 17 * 2511323117141749810813
137417 * 13 * 1511409613196338184647267
1374759 * 233166686668442666684426
1398111 * 31 * 411102411024124631024
1449143 * 3371722541291131095471
1570923 * 6831717796389132241612214
158417 * 31 * 73111679011
167055 * 13 * 25714096146654096114391
187053 * 5 * 29 * 43115516180104361436
1872197 * 193111833411833418334
1995171 * 281114840646264621484014840
230013 * 11 * 17 * 411211981353113531114401
2337797 * 241198708022018116004
257613 * 31 * 27711733425600197832560022438
2934113 * 37 * 611111118057
301217 * 13 * 331125572212951925212959542
3088917 * 23 * 79118181818181818181
3141789 * 3531158431584325811115843
3160973 * 4331140901102415341409014090
31621103 * 307111287624731287612876

Chaque case qui comporte la valeur 1 correspond à un entier a (dont la valeur figure en tête de colonne) menteur pour n (dont la valeur figure en début de ligne). Un menteur est inversible (mod n), et est donc nécessairement premier avec n ; les lignes comportant beaucoup de 1 correspondent, dans cette table, aux nombres de Carmichael, pour lesquels tout entier a premier avec n est menteur. Un nombre de Carmichael n est caractérisé par les propriétés suivantes :

Par exemple 6601 = 7 * 23 * 41 et 6600 = 23 * 3 * 52 * 11 est divisible par 6, 22 et 40. Tout test de Fermat effectué en calculant a6600 avec a non divisible par 7, ni par 23, ni par 41 fera croire que 6601 est premier.

Test de Miller-Rabin

La table suivante indique le comportement du test de Miller-Rabin pour tous les menteurs (inférieurs ou égaux à 7) de la table précédente ; chaque case comporte la suite de carrés successifs :
p0 = ae, p1 = a2e, p2 = a4e, p3 = a8e, ... pk = an-1
jusqu'à la valeur 1 ou -1. La première colonne (base 2), par exemple, se lit comme suit :

Factorisation
de n - 1
2357
3414 * 8532, 1
56116 * 35263, 166, 67, 123, 529, 463, 67, 1241, 298, 166, 67, 1
6454 * 161257, 259, 1
110516 * 69967, 259, 781, 11093, 144, 846, 781, 1827, 1039, 1041, 781, 1
13872 * 693512, 1
172964 * 27645, 1065, 1664, 11217, 1065, 1
190516 * 119128, 1144, 1
20472 * 10231
246532 * 771902, 1449, 1886, 12018, 144, 1016, 1886, 12437, 784, 871, 1886, 1
27014 * 6752337, 147, 12071, 2554, 1
28214 * 7052605, 1520, 11301, 1993, 1520, 1
32774 * 819128, -11016, 1
403364 * 633521, -1
436916 * 2732, 4, 16, 256, 1
43712 * 21852915, 1
46818 * 5851
54614 * 1365128, 1-1
66018 * 8252738, 4509, 13037, 1772, 4509, 13863, 4509, 1
79574 * 1989512, 7520, 1
8321128 * 658192, -12013, 8163, 1
848132 * 2653596, 6172, 5413, 7195, 1
89112 * 44556364, 1-12813, 1
102614 * 25651985, 1
105858 * 13237958, 10294, 18422, -15453, 1944, 291, 1
113058 * 141310487, 2129, 10641, 1
12801512 * 253011, 3013, 2260, 111045, 11296, 12049, 2260, 1
137414 * 34355286, 6343, 1
137472 * 68739321, 1
139814 * 34954806, 1024, 15116, 1024, 1
144912 * 724510448, 1
157094 * 39272048, 1
1584132 * 495112802, 218, 13380, 3039, 218, 1
1670564 * 2619027, 16444, 1301, 5396, 1
1870516 * 11692192, 16384, 1
1872132 * 585512, 50, 2500, 15907, 18334, 1962, 8115, 11468, -19852, 12240, 12158, 14669, 387, 1
199512 * 99756462, 1
230018 * 287516532, 9142, 13531, 1
2337716 * 146116599, 5479, 3373, 15907, 1
2576132 * 8053938, 25483, 1
293414 * 733526424, -122569, 115127, 25011, 123496, 11101, 1
301218 * 3765330, 18537, 1
308898 * 386118171, 12720, 1818, 1
314178 * 39278189, 15843, 10236, 1
316098 * 395119200, 15842, 25113, 1
316214 * 790531313, 1-1
Factorisation
de n - 1
2357

On voit que seulement 7 sur 45 (resp. 4 sur 12, 1 sur 10 et 0 sur 8) entiers pseudo-premiers pour la base 2 (resp. les bases 3, 5 et 7) sont fortement pseudo-premiers. Aucun entier de la table n'est fortement pseudo-premier simultanément pour les bases 2 et 3.

En fait le plus petit entier fortement pseudo-premier simultanément pour les bases 2 et 3 est supérieur à 106. Voici la table de comparaison des tests de Fermat et de Miller-Rabin de ce point de vue ; la troisième ligne, par exemple, se lit comme suit :

FermatMiller-Rabin
23412047
2, 311051 373 653
2, 3, 5172925 326 001
2, 3, 5, 7293413 215 031 751
2, 3, 5, 7, 11293412 152 302 898 747