Test de Fermat en base 2
2340 ≡ 1 (mod 341)
Le résultat vaut 1 : n est probablement premier. Le test ne prouve rien dans ce sens, il faut essayer d'autres bases.
Vérité : 341 est composé, 11 × 31. La base 2 est un « menteur » : elle laisse passer un nombre composé.
Exponentiation rapide
Plutôt que 340 multiplications, on lit l'exposant en binaire (101010100) : pour chaque chiffre on élève au carré, et si c'est un 1 on multiplie par 2, toujours modulo 341. Soit 9 étapes.
| bit | carré | × 2 | reste |
|---|---|---|---|
| 1 | 1 | oui | 2 |
| 0 | 4 | 4 | |
| 1 | 16 | oui | 32 |
| 0 | 1 | 1 | |
| 1 | 1 | oui | 2 |
| 0 | 4 | 4 | |
| 1 | 16 | oui | 32 |
| 0 | 1 | 1 | |
| 0 | 1 | 1 |
Toutes les bases de 1 à 340 : ■ 100 disent « premier », ■ 200 prouvent que n est composé, ■ 40 ont un facteur commun avec n. n est composé et 33 % des bases premières avec lui mentent. Touchez une case pour choisir la base.
Les menteurs de la base 2 jusqu'à 20 000
Ces nombres composés passent le test en base 2 : ce sont ses pseudo-premiers (36). Touchez-en un.
← Galerie
eCoucouv2.0.1Test de primalité de Fermat