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

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

Il est présent dans le JDK depuis assez longtemps, donc cela signifie qu'il doit avoir des utilisations. Mes connaissances limitées en informatique et en algorithmes (et en mathématiques) me disent qu'il n'est pas vraiment logique de savoir si un nombre est "probablement" un nombre premier mais pas exactement un nombre premier.

Alors, quel est un scénario possible où l'on voudrait utiliser cette méthode? Cryptographie?

Oui, cette méthode peut être utilisée en cryptographie. Cryptage RSA implique la recherche de nombres premiers énormes, parfois de l'ordre de 1024 bits (environ 300 chiffres). La sécurité de RSA dépend du fait que la factorisation d'un nombre composé de 2 de ces nombres premiers multipliés ensemble est extrêmement difficile et prend du temps. Mais pour que cela fonctionne, ils doivent être de premier ordre.

Il s'avère que prouver ces nombres premiers est également difficile. Mais le test de primalité de Miller-Rabin , l'un des tests de primalité utilisé par isProbablePrime, détecte qu'un nombre est composé ou ne donne aucune conclusion. L'exécution de ces ndurées de test vous permet de conclure qu'il y a 1 chance sur 2 ⁿ que ce nombre soit vraiment composite. L'exécution de plusieurs 100fois donne le risque acceptable de 1 sur 2 ¹⁰⁰ que ce nombre soit composite.

Si le test vous dit qu'un entier n'est pas premier , vous pouvez certainement croire que 100%.

Ce n'est que l'autre côté de la question, si le test vous dit qu'un entier est "un premier probable", que vous pouvez avoir un doute. La répétition du test avec des "bases" variables permet de rendre la probabilité de réussir à "imiter" un premier (étant un pseudo-premier fort par rapport à plusieurs bases) aussi petite que souhaité.

L'utilité du test réside dans sa rapidité et sa simplicité. On ne serait pas nécessairement satisfait du statut de "premier probable" comme réponse finale, mais on éviterait certainement de perdre du temps sur presque tous les nombres composites en utilisant cette routine avant de faire appel aux gros canons des tests de primalité .

La comparaison avec la difficulté de factoriser des 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 en effet il existe une preuve qu'une extension du test de Miller-Rabin à suffisamment de bases est définitive (dans la détection des nombres premiers, par opposition aux nombres premiers probables), mais ceci suppose l'hypothèse de Riemann généralisée, donc ce n'est pas aussi certain que le test de primalité AKS (plus cher) .

Le cas d'utilisation standard pour BigInteger.isProbablePrime(int)est dans la cryptographie. Plus précisément, certains algorithmes cryptographiques, tels que RSA , nécessitent de grands nombres premiers choisis au hasard. Mais il est important de noter que ces algorithmes n'exigent pas vraiment que ces nombres soient garantis comme étant premiers - ils doivent simplement être premiers avec un très probabilité élevée.

Quelle est la hauteur très élevée? Eh bien, dans une application de cryptographie, on appelle 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 à un sur 2 ¹²⁸ ou 2 ²⁵⁶ .

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 que la primalité de ces nombres a été testée avec .isProbablePrime(128), vous s'attendrait, 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 fonctionner pendant des centaines de milliards d'années sans subir de panne matérielle. Dans la pratique, cependant, il est beaucoup plus probable qu'un rayon cosmique aléatoire frappe votre ordinateur au bon moment et au bon endroit pour faire basculer la valeur de retour.isProbablePrime(128) de faux à vrai, sans provoquer d'autres effets détectables, que pour un non -prime nombre pour réussir le test de primalité probabiliste à ce niveau de certitude.

Bien sûr, le même risque de rayons cosmiques aléatoires et d'autres défauts matériels s'applique également aux tests de primalité déterministe comme AKS . Ainsi, en pratique, même ces tests ont un (très petit) taux de faux positifs de base en raison de pannes matérielles aléatoires (sans parler de toutes les autres sources possibles d'erreurs, telles que les bogues d'implémentation).

Puisqu'il est facile de pousser le taux intrinsèque de faux positifs du test de primalité de Miller – Rabin utilisé de .isProbablePrime()loin en dessous de ce taux de base, simplement en répétant le test suffisamment de fois, et puisque, même répété tant de fois, le test de Miller – Rabin est toujours beaucoup plus rapide en pratique que les tests de primalité déterministe les plus connus comme AKS, il reste le test de primalité standard pour les applications cryptographiques.

(De plus, 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 (ou rarement plus) nombres premiers d'environ 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 attraper), l'algorithme RSA fonctionnent toujours très bien, et la clé, bien qu'un peu plus faible contre certains types d'attaques que les clés RSA normales de même longueur, devrait toujours être raisonnablement sécurisée si vous n'avez pas lésiné inutilement sur la longueur de la clé.)

Un cas d'utilisation possible est de tester la primalité d'un nombre donné (lors d'un test qui en soi a de nombreuses utilisations). L' isProbablePrimealgorithme s'exécutera beaucoup plus rapidement qu'un algorithme exact, donc si le nombre échoue isProbablePrime, alors il n'est pas nécessaire d'aller au détriment de l'exécution de l'algorithme le plus cher.

Trouver des nombres premiers probables est un problème important en cryptographie. Il s'avère qu'une stratégie raisonnable pour trouver un probable k-bit premier est de sélectionner à plusieurs reprises un nombre aléatoire de k-bit, et de le tester pour la primalité probable en utilisant une méthode comme isProbablePrime().

Pour plus d'informations, voir la section 4.4.1 du Handbook of Applied Cryptography .

Voir également Sur 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 isProbablePrimeméthode a é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 laps de temps raisonnable. L'approche la plus connue à l'époque était l' algorithme de Miller-Rabin - un algorithme probabiliste qui donnait parfois de faux positifs (c'est-à-dire signalait les non-nombres premiers comme des nombres premiers), mais pouvait être réglé pour réduire la probabilité de faux positifs, au détriment d'augmentations modestes 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 premier assez rapidement, 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.

Une meilleure question est peut-être de savoir pourquoi aucune isPrimeméthode n'a été ajoutée au JDK depuis 2002.