java - BigInteger 的 .isProbablePrime() 的可能用例是什么？

Question

The method BigInteger.isProbablePrime()很奇怪；从文档中，这将判断一个数字是否为素数，概率为 1 - 1/2^arg，其中 arg 是整数参数。

它在JDK中已经存在很长时间了，所以它意味着它必须有用途。我在计算机科学和算法(以及数学)方面的有限知识告诉我，知道一个数字是否“可能”是素数但不完全是素数是没有意义的。

那么，想使用这种方法的可能场景是什么？密码学？

Answer 1

是的，这种方法可以用于密码学。 RSA encryption涉及寻找巨大的素数，有时大约为 1024 位(约 300 位)。 RSA 的安全性取决于这样一个事实，即对由 2 个质数相乘组成的数进行因式分解是极其困难且耗时的。但要使其发挥作用，它们必须是素数。

事实证明，证明这些素数也很困难。但是 Miller-Rabin primality test ，isProbablePrime 使用的素数测试之一，要么检测到一个数字是合数，要么不给出结论。运行此测试 n 次可以得出结论，有 2 分之一的可能性ⁿ 表示这个数字确实是复合的。运行 100 次会产生可接受的风险，即 2¹⁰⁰ 中有 1 个是复合数字。