Test Miller–Rabin déterministe

Le test de Miller–Rabin déterministe décide si un entier n est premier en appliquant le test de témoin de nombre premier probable fort à une liste courte et fixe de bases connues pour trancher tout entier sous une borne de garantie publiée. Contrairement à une exécution probabiliste de Miller–Rabin qui tire des témoins au hasard et n’estime que l’erreur, cette capacité utilise toujours les mêmes bases, renvoie toujours le même verdict pour le même n, et refuse toute entrée au-dessus de la borne où ces bases ne sont plus prouvées suffisantes. Vous envoyez un unique entier au moins égal à deux et au plus égal à la borne, et vous recevez un indicateur de primalité, la liste des témoins, la borne elle-même et—si le nombre est composé—le premier témoin qui l’a prouvé.

Fonctionnement du test de premier probable fort à bases fixes

Miller–Rabin réécrit un candidat impair n comme n moins un égal à d fois deux à la puissance s avec d impair, puis pour chaque témoin a calcule a à la puissance d modulo n. Si cette puissance vaut un ou n moins un, le témoin réussit. Sinon l’algorithme élève la valeur au carré jusqu’à s moins une fois et n’accepte le témoin que si un carré intermédiaire vaut n moins un ; tout autre chemin prouve que n est composé pour cette base.

Un nombre qui réussit tous les témoins est appelé premier probable fort pour ces bases. Pour des ensembles fixes soigneusement choisis, des résultats de théorie des nombres montrent qu’aucun composé sous un seuil connu ne trompe toutes les bases de l’ensemble—ainsi le résultat de premier probable devient un vrai premier à l’intérieur de la borne. Cette capacité utilise les sept bases deux, trois, cinq, sept, onze, treize et vingt-trois, suffisantes pour tout entier de soixante-quatre bits et donc pour tout entier sûr JavaScript jusqu’à neuf quadrillions.

Les tout petits premiers deux et trois sont tranchés comme premiers. Lorsqu’un témoin divise n et est plus petit que n, ce témoin est signalé comme base défaillante car n est un multiple évident.

Quand un test de primalité à bases fixes aide

Les cours de cryptographie et les formateurs CTF utilisent un test de Miller–Rabin déterministe pour montrer aux étudiants la différence entre des contrôles probabilistes à témoins aléatoires et des certificats à bases fixes qui nomment leur borne de garantie dans la réponse. Les auteurs de bibliothèques ancrent des tests unitaires contre des premiers connus, des pseudopremiers forts et des composés pour qu’un refactoring de l’exponentiation modulaire ne bascule pas un verdict en silence.

Les développeurs d’applications valident des valeurs de configuration de forme première, des graines de puzzle ou des paramètres jouet Diffie–Hellman avant un pipeline plus long, en capturant les pairs et les petits composés sans déployer un système d’algèbre computationnelle.

Préférez cet outil lorsque l’intention de recherche est précisément l’algorithme de Miller–Rabin déterministe avec témoins fixes et borne dure—non lorsque vous avez besoin du plus petit diviseur d’un composé, d’une factorisation première complète, de Lucas–Lehmer pour les nombres de Mersenne, ou de tests probabilistes avec une liste de témoins personnalisée que vous fournissez vous-même.