BigInteger的.isProbablePrime（）可能的用例是什么？
BigInteger.isProbablePrime（）方法很奇怪， 从文档中，这将告诉一个数是否为1 - 1 / 2^arg的概率，其中arg是整数参数。
它已经在JDK中出现了相当长的时间，所以这意味着它必须有用处。 我对计算机科学和algorithm（以及math）知识的有限性告诉我，知道一个数字是否“可能”是一个素数但不完全是一个素数是没有意义的。
那么，什么是可能的情况下，人们会想要使用这种方法？ 密码？
是的，这个方法可以用在密码学中。 RSAencryption涉及到巨大的素数的发现，有时在1024位（约300位）的数量级。 RSA的安全性取决于这样一个事实，即把乘以这些素数中的两个的数字相乘是非常困难和耗时的。 但是为了工作，他们必须是最好的。
事实certificate，certificate这些数字素数也是困难的。 而Miller-Rabin素数检验 ，其中一个素数检验使用的是isProbablePrime ，要么检测到一个数是复合的，要么就没有结论。 运行这个testingn次可以让你得出结论：这个数字真的是复合的，有1/2的几率。 运行100次会产生1比2的100的可接受风险，这个数字是合成的。
如果testing告诉你一个整数不是素数 ，那么你当然可以相信100％。
这只是问题的另一面，如果testing告诉你一个整数是“一个可能的素数”，那么你可能会怀疑。 用不同的“碱基”来重复testing，可以使假想的“模仿”素数（相对于多个碱基而言是一个强的伪质）的概率尽可能小。
testing的有用性在于其速度和简单性。 人们不一定会满意“可能的素数”作为最终答案的地位，但是在引入素性testing的大炮之前，通过使用这个例程，肯定会避免在几乎所有的复合数字上浪费时间。
与整数分解难度的比较是一个红鲱鱼的东西。 众所周知，整数的正整数可以用多项式时间来确定，事实上certificate了Miller-Rabin检验扩展到足够多的碱基是确定的（检测素数，而不是可能的素数），但是这个假定广义黎曼假设，所以它不像（更昂贵的） AKS素数检验那么确定。
BigInteger.isProbablePrime(int)的标准用例在encryption中。 具体来说，某些密码algorithm（如RSA ）需要随机select大的素数。 然而重要的是，这些algorithm并不需要这些数字能够保证成为素数 – 他们只需要以非常高的概率进行素数。
有多高？ 那么，在一个encryption应用程序中，通常会调用.isProbablePrime() ，其参数介于128到256之间。因此，通过这样一个testing的非素数的概率小于2 128或2 256中的一个 。
让我们来看一下：如果你有100亿台计算机，每台计算机每秒产生10亿个可能的素数（这意味着在任何现代CPU上每个数字less于一个时钟周期），并用.isProbablePrime(128) ，那么平均而言，您将会期望一个非素数在每1000亿年内滑入一次 。
也就是说，如果这100亿台电脑能以某种方式运行数千亿年，而不会遇到任何硬件故障，情况就是如此。 然而，在实践中， 随机宇宙射线更有可能在适当的时间和地点触发你的计算机，将 .isProbablePrime(128) 的返回值从假转换为真，而不会引起任何其他可检测的效果，实际上在这个确定性水平上通过概率素性testing是一个非素数。
当然，随机宇宙射线和其他硬件故障的相同风险也适用于像AKS这样的确定性素性testing。 因此，实际上，即使这些testing由于随机硬件故障（更不用说所有其他可能的错误来源，例如执行错误），也具有（非常小的）基线误报率。
由于.isProbablePrime()所使用的Miller-Rabin素数检验的内在假阳性率很容易远低于这个基线比率，所以只需要重复testing足够多次，而且因为即使重复了很多次，Miller-拉宾testing在实践中的速度仍然比最知名的确定性素数testing（如AKS）快得多，它仍然是密码应用的标准素性testing。
（除此之外，即使偶然select一个强假折射率作为RSA弹性模量的因素之一，通常也不会导致灾难性的失败。通常，这种假折射率将是两个（或者很less）更多的大约一半的长度，这意味着你最终会得到一个多重RSA密钥，只要没有一个因素太小 （如果它们是，素数testing应该抓住它们），RSAalgorithm将会仍然可以正常工作，而且对于某些types的攻击，如果你没有不必要地在密钥长度上吝啬，那么攻击者的密钥虽然比普通的RSA密钥稍微弱一些，但仍然应该是合理的。
一个可能的用例是testing给定数字的原始性（在testing本身有很多用途）。 isProbablePrimealgorithm的运行速度比精确的algorithm要快得多，所以如果数字失败isProbablePrime ，那么就不需要花费更多昂贵的algorithm。
发现可能的素数是密码学中的一个重要问题。 事实certificate，find一个可能的k位素数的一个合理的策略是重复select一个随机的k位数，并使用像isProbablePrime()这样的方法testing其可能的素数。
有关进一步讨论，请参阅应用密码术手册第4.4.1节 。
另请参见Brandt和Damgård的渐进式search关于可能素数的生成 。
诸如RSA密钥生成之类的algorithm依赖于能够确定数字是否为素数。
然而，在JDK（1997年2月）中增加了isProbablePrime方法的时候，没有一种可靠的方法可以在合理的时间内确定一个数字是否为主数据。 当时最为人所知的方法是Miller-Rabinalgorithm – 一种有时会给出误报的概率algorithm（即将报告非素数作为素数），但可以调整以减less误报的可能性，代价是运行时适度增加。
从那以后，已经发现的algorithm可以确定性地确定一个数是否合理快速地发生，例如2002年8月发现的AKSalgorithm 。然而，应该指出的是，这些algorithm仍然不如Miller-Rabin那么快。
也许更好的问题是自2002年以来为什么没有isPrime方法被添加到JDK。
