Quel est un cas d’utilisation possible de .isProbablePrime () de BigInteger?

La méthode BigInteger.isProbablePrime() est assez étrange. à partir de la documentation, cela dira si un nombre est premier avec une probabilité de 1 - 1 / 2^arg , où arg est l’argument entier.

Il est présent dans le JDK depuis assez longtemps, ce qui signifie qu’il doit être utilisé. Ma connaissance limitée de l’informatique et des algorithmes (et des mathématiques) me dit que cela n’a pas vraiment de sens de savoir si un nombre est «probablement» un facteur primordial, mais pas exactement.

Alors, quel est un scénario possible où l’on voudrait utiliser cette méthode? La cryptographie?

Oui, cette méthode peut être utilisée en cryptographie. Le cryptage RSA implique la recherche de grands nombres premiers, parfois de l’ordre de 1024 bits (environ 300 chiffres). La sécurité de RSA dépend du fait qu’il est extrêmement difficile et fastidieux de prendre en compte un nombre composé de deux de ces nombres premiers. Mais pour que cela fonctionne, ils doivent être premiers.

Il s’avère que prouver ces nombres premiers est difficile aussi. Mais le test de primalité de Miller-Rabin , l’un des tests de primalité utilisés par isProbablePrime , détecte qu’un nombre est composite ou ne donne aucune conclusion. L’exécution de ce test n fois vous permet de conclure qu’il existe une cote de 1 sur 2 n pour que ce nombre soit réellement composite. Le faire 100 fois donne le risque acceptable de 1 sur 2 100 que ce nombre soit composite.

Si le test vous dit qu’un nombre entier n’est pas premier , vous pouvez certainement le croire à 100%.

Ce n’est que le revers de la question, si le test vous dit qu’un nombre entier est “un nombre premier probable”, que vous pouvez avoir des doutes. Répéter le test avec des “bases” variables permet de rendre la probabilité de réussir à “imiter” un nombre premier (étant un pseudo-prime fort par rapport à plusieurs bases) aussi faible que souhaité.

L’utilité du test réside dans sa rapidité et sa simplicité. On ne serait pas nécessairement satisfait du statut de “prime probable” comme réponse finale, mais on éviterait certainement de perdre du temps sur presque tous les nombres composites en utilisant cette routine avant d’introduire les grosses armes de test de primalité .

La comparaison avec la difficulté de factoriser les entiers est en quelque sorte un hareng rouge. On sait que la primalité d’un entier peut être déterminée en temps polynomial, et il existe en effet une preuve qu’une extension du test de Miller-Rabin à suffisamment de bases est définitive (en détectant des nombres premiers, par opposition aux nombres premiers probables), mais ceci suppose l’hypothèse de Riemann généralisée, elle n’est donc pas aussi sûre que le test de primalité AKS (plus coûteux).

Le cas d’utilisation standard de BigInteger.isProbablePrime(int) est la cryptographie. Plus précisément, certains algorithmes cryptographiques, tels que RSA , requièrent des grands nombres premiers choisis de manière aléatoire. Ce qui est important, cependant, ces algorithmes n’exigent pas vraiment que ces nombres soient garantis comme prime – ils ont juste besoin d’être avec une probabilité très élevée.

Quelle est la hauteur très élevée? Eh bien, dans une application cryptographique, on appellerait généralement .isProbablePrime() avec un argument entre 128 et 256. Ainsi, la probabilité qu’un nombre non premier passe un tel test est inférieure à 1 sur 2 128 ou 2 256 .

Mettons cela en perspective: si vous aviez 10 milliards d’ordinateurs, chacun générant 10 milliards de nombres premiers probables par seconde (ce qui signifierait moins d’un cycle d’horloge par nombre sur n’importe quel processeur moderne), et la primalité de ces nombres a été testée avec .isProbablePrime(128) , vous vous attendez en moyenne à ce qu’un nombre non premier se glisse une fois tous les 100 milliards d’années .

Autrement dit, ce serait le cas si ces 10 milliards d’ordinateurs pouvaient tous durer des centaines de milliards d’années sans connaître de défaillance matérielle. En pratique, cependant, il est beaucoup plus probable qu’un rayon cosmique aléatoire frappe votre ordinateur au bon moment et au bon endroit pour retourner la valeur de retour de .isProbablePrime(128) de faux à vrai, sans provoquer d’autres effets détectables, que c’est à un nombre non premier de passer le test de primalité probabiliste à ce niveau de certitude.

Bien entendu, le même risque de rayons cosmiques aléatoires et d’autres défauts matériels s’applique également aux tests de primalité déterministes tels que le système AKS . Ainsi, dans la pratique, même ces tests ont un taux de faux positifs basique (très faible) dû à des défaillances matérielles aléatoires (sans parler de toutes les autres sources d’erreurs possibles, telles que les bogues d’implémentation).

Comme il est facile de pousser le taux de faux positifs insortingnsèque du test de primalité de Miller – Rabin utilisé par .isProbablePrime() bien en deçà de ce taux de base, simplement en répétant le test suffisamment de fois et Le test de Rabin est encore beaucoup plus rapide dans la pratique que les tests de primalité déterministes les plus connus, comme AKS. Il rest le test de primalité standard pour les applications cryptographiques.

(En outre, même si vous sélectionniez accidentellement un pseudoprime fort comme l’un des facteurs de votre module RSA, cela ne conduirait généralement pas à une défaillance catastrophique. En règle générale, ces pseudoprimes seraient des produits de deux nombres premiers (ou rarement plus) La moitié de la longueur, ce qui signifie que vous vous retrouveriez avec une clé RSA multi-prime . Tant qu’aucun des facteurs n’était trop petit (et s’ils l’étaient, le test de primalité aurait dû les détecter), l’algorithme RSA fonctionne toujours correctement, et la clé, même si elle est légèrement plus faible contre certains types d’attaques que les clés RSA normales de même longueur, devrait quand même être raisonnablement sécurisée si vous ne lésinez pas inutilement sur la longueur de la clé.

Un cas d’utilisation possible est de tester la primalité d’un nombre donné (au test qui en soi a de nombreuses utilisations). L’algorithme isProbablePrime s’exécutera beaucoup plus rapidement qu’un algorithme exact. Par conséquent, si le nombre échoue dans isProbablePrime , il n’est pas nécessaire d’utiliser l’algorithme plus coûteux.

La recherche de nombres premiers probables est un problème important en cryptographie. Il s’avère qu’une stratégie raisonnable pour trouver un nombre premier probable de bits k consiste à sélectionner de manière répétée un nombre aléatoire de k bits, et à le tester pour une primalité probable en utilisant une méthode comme isProbablePrime() .

Pour plus de détails, voir la section 4.4.1 du Manuel de cryptographie appliquée .

Voir également la génération de nombres premiers probables par recherche incrémentale par Brandt et Damgård.

Les algorithmes tels que la génération de clé RSA reposent sur la capacité de déterminer si un nombre est premier ou non.

Cependant, au moment où la méthode isProbablePrime été ajoutée au JDK (février 1997), il n’existait aucun moyen éprouvé de décider de manière déterministe si un nombre était premier dans un délai raisonnable. L’approche la plus connue à ce moment-là était l’ algorithme de Miller-Rabin – un algorithme probabiliste qui donnerait parfois de faux positifs (c.-à-d. Qu’il rapporterait les non-nombres premiers), mais pourrait être ajusté pour réduire le risque de faux positifs. de modestes augmentations du temps d’exécution.

Depuis lors, des algorithmes ont été découverts qui peuvent déterminer de manière déterministe si un nombre est raisonnablement rapide, comme l’ algorithme AKS découvert en août 2002. Cependant, il convient de noter que ces algorithmes ne sont toujours pas aussi rapides que Miller-Rabin.

Peut-être une meilleure question est de savoir pourquoi aucune méthode isPrime n’a été ajoutée au JDK depuis 2002.