Ce qui est un cas d'utilisation possible de BigInteger.isProbablePrime ()?
la méthode BigInteger.isProbablePrime() est assez étrange; de la documentation, cela indiquera 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, donc il signifie qu'il doit avoir des utilisations. Ma connaissance limitée de l'informatique et des algorithmes (et des mathématiques) me dit qu'il n'est pas vraiment logique de savoir si un nombre est "probablement" le premier, mais pas exactement un nombre premier.
alors, quel est un scénario possible où l'on voudrait utiliser cette méthode? La cryptographie?
6 réponses
Oui, cette méthode peut être utilisée en cryptographie. RSA encryption implique la recherche d'énormes nombres premiers, parfois de l'ordre de 1024 bits (environ 300 chiffres). La sécurité de RSA dépend du fait que factoriser un nombre qui se compose de 2 de ces nombres premiers multipliés ensemble est extrêmement difficile et prend du temps. Mais pour que ça marche, ils doivent être premiers.
il s'avère que prouver ces nombres premiers est difficile trop. Mais le Miller-Rabin primality test , l'un des tests de primalité utilisés par isProbablePrime , soit 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 ya un 1 en 2 n chances que ce nombre est vraiment composite. Le fait de l'exécuter 100 fois donne le risque acceptable de 1 sur 2 100 que ce nombre est composé.
si le test vous dit qu'un entier est pas premier , vous pouvez certainement croire que 100%.
c'est seulement l'autre côté de la question, si le test vous dit un entier est" un premier probable", que vous pouvez entretenir le doute. En répétant le test avec des "bases" variables, la probabilité de réussir faussement à "imiter" un premier (étant un pseudo-premier fort par rapport à plusieurs bases) peut être réduite autant que désiré.
l'utilité de l'essai réside dans sa vitesse 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 numéros composés par en utilisant cette routine avant d'apporter les gros canons de test de primalité .
la comparaison de La difficulté de la factorisation d'entiers est quelque chose d'un hareng rouge. Il est connu que la primalité d'un entier peut être déterminé en temps polynomial, et en effet il y a une preuve qu'une extension du test de Miller-Rabin à suffisamment de bases est définitive (en détectant des nombres premiers, par opposition à des nombres premiers probables), mais cela suppose L'hypothèse généralisée de Riemann, de sorte qu'il n'est pas tout à fait certain que le (plus cher) AKS primality test .
le cas d'utilisation standard pour BigInteger.isProbablePrime(int) est en cryptographie. Plus précisément, certains algorithmes cryptographiques , tels que RSA , nécessitent de grands nombres premiers choisis au hasard. Fait important, cependant, ces algorithmes ne nécessitent pas vraiment ces nombres d'être garanti pour être premier - ils ont juste besoin d'être premier avec un très haute probabilité.
quelle hauteur est très haute? Eh bien, dans une application crypto, on appellerait typiquement .isProbablePrime() avec un argument entre 128 et 256. Ainsi, la probabilité qu'un nombre non premier réussisse un tel test est inférieure à un 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 moderne CPU), et la primalité de ces nombres a été testé avec .isProbablePrime(128) , vous vous attendriez, en moyenne, un nombre non-prime à glisser dans une fois tous les 100 milliards d'années .
c'est-à-dire, ce serait le cas, si ces 10 milliards d'ordinateurs pouvaient en quelque sorte tous fonctionner pendant des centaines de milliards d'années sans éprouver n'importe quelles pannes matérielles. En pratique, cependant, c'est beaucoup plus probable pour un rayon cosmique aléatoire frapper votre ordinateur juste au bon moment et au bon endroit pour retourner la valeur de retour de .isProbablePrime(128) de false à true, sans causer d'autres effets détectables, que c'est pour un nombre non-premier de passer réellement 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 déterministes de primalité comme AKS . Ainsi, dans la pratique, même ces tests ont un taux de faux positifs de base (très faible) dû à des 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 positif du test de primalité de Miller–Rabin utilisé par .isProbablePrime() bien au-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 encore beaucoup plus rapide dans la pratique que les tests déterministes de primalité les plus connus comme les AK, il reste le test standard de primalité pour les applications cryptographiques.
(D'ailleurs, même si vous avez accidentellement sélectionné un pseudoprime fort comme l'un des facteurs de votre module RSA, il ne conduirait généralement pas à une défaillance catastrophique. Typiquement, de tels pseudoprimes seraient produits de deux (ou rarement plus) nombres premiers d'environ la moitié de la longueur, ce qui signifie que vous finissez avec une clé RSA multi-prime . Aussi longtemps qu'aucun des facteurs n'était trop petit (et s'ils l'étaient, le test de primalité aurait dû les attraper), l'algorithme RSA fonctionnera toujours très bien, et la clé, bien que légèrement plus faible contre certains types d'attaques que les clés RSA normales de la même longueur, devrait toujours être raisonnablement sûr si vous ne lésinez pas inutilement sur la longueur de la clé.)
un cas d'utilisation possible est dans l'essai de primalité d'un nombre donné (à l'essai qui en lui-même a de nombreuses utilisations). L'algorithme isProbablePrime fonctionnera beaucoup plus vite qu'un algorithme exact, donc si le nombre échoue isProbablePrime , alors on n'a pas besoin d'aller aux frais de l'exécution de l'algorithme Plus cher.
trouver nombres premiers probables est un problème important en cryptographie. Il s'avère qu'une stratégie raisonnable pour trouver un premier K-bit probable est de sélectionner à plusieurs reprises un nombre k-bit aléatoire, et de le tester pour la primalité probable en utilisant une méthode comme isProbablePrime() .
pour plus de détails, voir section 4.4.1 du Handbook of Applied Cryptography .
Voir aussi sur génération de nombres premiers probables par recherche incrémentale par Brandt et Damgård.
tels que la génération de clés RSA dépendent de leur capacité à déterminer si un nombre est Premier ou non.
toutefois, au moment où la méthode isProbablePrime a été ajoutée à la JDK (février 1997), il n'y avait aucune façon prouvée de décider de façon déterministe si un nombre était premier dans un délai raisonnable. L'approche la plus connue à cette époque était l'algorithme de Miller-Rabin - un algorithme probabiliste qui donnerait parfois faux positifs (I. e, signalerait les non-primes comme des primes), mais pourrait être accordé pour réduire la probabilité de faux positifs, au détriment des augmentations modestes dans le temps d'exécution.
depuis lors, des algorithmes ont été découverts qui peuvent décider de façon déterministe si un nombre est premier raisonnablement rapidement, comme le AKS algorithme qui a été découvert en août 2002. Toutefois, 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 la méthode isPrime n'a pas été ajoutée à la JDK depuis 2002.