Vérificateur de primalité

Le vérificateur de primalité vous indique si un entier est premier et, contrairement à la plupart des calculatrices en ligne, vous montre l'algorithme qui l'a prouvé, et non une table de recherche mise en cache. Tapez n'importe quel entier, positif ou négatif, petit ou énorme, et l'outil décide quel algorithme réel exécuter en fonction de sa taille.

Pour les nombres inférieurs à 10¹² (un billion), il exécute une véritable division d'essai : à partir de 2, il essaie chaque candidat entier jusqu'au plancher de √n comme diviseur possible, s'arrêtant au moment où l'on divise uniformément (composite) ou confirmant qu'aucun nombre entier ne le fait une fois que chaque candidat jusqu'à √n a été vérifié (premier). Pour un grand nombre de candidats, la trace affichée est limitée aux ~ 18 premiers essayés plus le dernier, avec une note honnête sur le nombre de candidats ignorés à l'écran - mais chaque candidat est toujours réellement vérifié par le code, aucun n'est ignoré dans le calcul.

Pour les nombres égaux ou supérieurs à ce seuil – la plage de taille utilisée en cryptographie – la division de première instance prendrait trop de temps, de sorte que l'outil passe au test de primalité de Miller-Rabin avec un ensemble fixe et déterministe de 13 témoins principaux (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Cet ensemble de témoins exact est un résultat bien connu : il n'a aucun faux positif pour tout n inférieur à 3 317 044 064 679 887 385 961 981 (environ 3,3 × 10²⁴), une limite établie par vérification informatique (voir Sorenson & Webster, 2015, et le tableau de témoins déterministes largement reproduit auquel il appartient). Au-dessus de cette limite, le même test s'exécute toujours, mais l'outil vous dit honnêtement que la garantie devient une garantie probabiliste extrêmement forte plutôt qu'une certitude mathématique.

La trace Miller-Rabin écrit n − 1 = 2ˢ × d avec d impair, puis parcourt une véritable exponentiation modulaire BigInt — carré et multiplication, réduisant le modulo n à chaque étape afin que les nombres n'explosent jamais — petit à petit pour le premier témoin, et rapporte le verdict de chaque témoin, y compris quel témoin prouve la composition si le nombre s'avère n'être pas premier. Tout s'exécute localement dans votre navigateur : pas de serveur, pas d'API externe, aucune donnée ne quitte jamais votre appareil.