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

Question

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

fge*_*fge 83 java primes

这种方法BigInteger.isProbablePrime()很奇怪; 从文档中,这将告诉一个数字是否是素数的概率1 - 1 / 2^arg,其中arg是整数参数.

它已经存在于JDK很长一段时间了,所以它意味着它必须有用.我在计算机科学和算法(以及数学)方面的有限知识告诉我,知道一个数字是否"可能"是一个素数而不是一个素数并不是真的有意义.

那么,人们想要使用这种方法的可能情况是什么？密码？

Answer 1

rge*_*man 67

是的,这种方法可以用于密码学. RSA加密涉及找到大量素数,有时大约为1024位(约300位).RSA的安全性取决于将由这些素数中的2个组成的数字因子相乘而非常困难且耗时的事实.但要使它发挥作用,它们必须是最重要的.

事实证明,证明这些数字是最重要的也是困难的.但米勒 - 拉宾素性测试,其中一个素数测试使用isProbablePrime,或者检测到一个数字是复合的还是没有给出结论.运行这个测试n的时间可以让你得出结论,有一个1 2 ^ñ赔率,这个数字实在是复合材料.运行它的100时间会产生1到2 ¹⁰⁰的可接受风险,这个数字是复合的.

@TedHopp该实现使用随机生成器,每一轮都有一个新的随机数,有3/4的机会检测到一个复合.默认生成器是SecureRandom,具有强大的随机性保证. (11认同)
`isProbablyPrime`的实现是(据我所知)完全确定的.如何运行测试`n`次提高了正确结果的几率？(即使它是随机性的一个元素,也需要让多个调用的随机性独立,以便以您描述的方式影响风险.) (5认同)
然而,可能很难记住PRIMES在P中.AKS测试可能比Miller-Rabin慢,但没有指数差异,或者它们之间的多项式.你可以使用Miller-Rabin找到一堆可能的素数并使用AKS来证明它们是素数. (4认同)
@ Mr.777我看过拉宾 - 米勒一两次,但米勒 - 拉宾几次.我不确定是否有官方名称. (3认同)
@ Mr.777上面我链接的维基百科页面首先提到"米勒 - 拉宾",但承认两个名字:"米勒 - 拉宾素性测试或拉宾 - 米勒素性测验". (3认同)

Answer 2

har*_*ath 20

如果测试告诉你一个整数不是素数,你当然可以相信100%.

这只是问题的另一面,如果测试告诉你一个整数是"可能的素数",你可能会怀疑.用不同的"基数"重复测试允许错误地成功地"模仿"素数(相对于多个碱基是强伪素数)的概率可以根据需要做得小.

测试的有用性在于它的速度和简单性.人们不一定会对"可能的素数"的状态作为最终答案感到满意,但是在引入素数测试的大枪之前,通过使用这个例程肯定会避免浪费时间在几乎所有的复合数上.

对整数分解难度的比较是一种红色的鲱鱼.众所周知,整数的素数可以在多项式时间内确定,实际上有证据证明米勒 - 拉宾检验扩展到足够多的基数是确定的(在检测质数时,与可能的素数相反),但这假设广义黎曼假设,因此它不太确定(更昂贵的)AKS素性测试.

值得注意的是,AKS仅在2002年8月被发现,而这种方法自2002年2月以来一直在JDK中使用 (4认同)
不,等等,这是自1997年2月以来一直在JDK中(我正在查看`probablePrime`方法,而不是`isProbablePrime`方法) (3认同)
对于在地质尺度上可计算的任何数量,AKS都非常慢,并且不会比APR-CL快,更不用说人类规模.APR-CL和ECPP已于1997年出现.正如Brett所提到的,如果我们需要证据,ECPP是一个不错的选择.与可能的主要方法(例如MR,BPSW,Frobenius)相比,所有这些都是缓慢的. (2认同)

Answer 3

Ilm*_*nen 18

标准用例BigInteger.isProbablePrime(int)是密码学.具体而言,某些加密算法(如RSA)需要随机选择的大质数.然而,重要的是,这些算法并不真正要求保证这些数字是素数 - 它们只需要以非常高的概率进行素数处理.

有多高？好吧,在加密应用程序中,人们通常会调用.isProbablePrime()介于128和256之间的参数.因此,通过此类测试的非素数的概率小于2 ¹²⁸或2 ^{256中的一个}.

让我们从视角来看:如果你有100亿台计算机,每台计算机每秒产生100亿个可能的素数(这意味着任何现代CPU上每个数字的时钟周期不到一个),并且这些数字的素数已经过测试了.isProbablePrime(128),你们平均而言,预计每1000亿年就会有一个非素数进入一次.

也就是说,如果这100亿台计算机能够以某种方式运行数千亿年而不会遇到任何硬件故障,那就是这种情况.但在实践中,这是一个随机的宇宙射线就很有可能在正确的时间和地点,以打击计算机翻转的返回值的.isProbablePrime(128)从虚假到真实的,不会造成任何其它可检测的效果,比它是一个非 - 在该确定级别实际通过概率素性测试的主要编号.

当然,随机宇宙射线和其他硬件故障的相同风险也适用于像AKS这样的确定性素性测试.因此,在实践中,即使这些测试由于随机硬件故障而具有(非常小的)基线误报率(更不用说所有其他可能的错误源,例如实现错误).

因为很容易推的内在假阳性率米勒-拉宾检验所用.isProbablePrime(),简单地通过重复测试足够多次,因为即使如此反复多次到目前为止这一基准利率之下,米勒-拉宾测试仍然是在实践中比最着名的确定性素性测试(如AKS)快得多,它仍然是加密应用的标准素性测试.

(此外,即使你偶然选择一个强的伪赝作为你的RSA模数的因素之一,它通常不会导致灾难性的失败.通常,这样的假赝品将是大约两个(或很少更多)素数的产物.长度的一半,这意味着你最终会得到一个多素数RSA密钥.只要没有一个因素太小(如果它们是,那么素数测试应该抓住它们),RSA算法将仍然工作得很好,关键,虽然对于某些类型的攻击比相同长度的普通RSA键有些弱,但如果你没有不必要地缩短密钥长度,那么它仍然应该是合理安全的.)

Answer 4

Ted*_*opp 8

一个可能的用例是测试给定数字的素数(在测试中,它本身有很多用途).该isProbablePrime算法的运行速度比精确算法要快得多,因此如果数字失败isProbablePrime,则无需担心运行更昂贵的算法.

@fge:因子分解确实在NP中,但我怀疑你的意思是"NP-complete",这个因子化是不知道的.相反,人们强烈怀疑它不是NP难的. (5认同)

Answer 5

NPE*_*NPE 6

找到可能的素数是密码学中的一个重要问题.事实证明,找到可能的k位素数的合理策略是重复选择随机k位数,并使用类似的方法测试它的可能素数isProbablePrime().

有关进一步的讨论,请参阅"应用密码学手册"第4.4.1节.

另见Brandt和Damgård 通过增量搜索生成可能的素数.

Answer 6

Jam*_*pic 5

诸如RSA密钥生成之类的算法依赖于能够确定数字是否是素数.

然而,在将该isProbablePrime方法添加到JDK(1997年2月)时,没有一种经过验证的方法可以确定地确定一个数字在合理的时间内是否为素数.当时最着名的方法是Miller-Rabin算法 - 一种概率算法,有时会产生误报(即,会将非素数报告为素数),但可以调整以减少误报的可能性,但需要付出代价.运行时适度增加.

从那时起,已经发现了可以确定性地确定数字是否合理快速的算法,例如2002年8月发现的AKS算法.但是,应该注意这些算法仍然没有Miller-Rabin那么快.

或许更好的问题是为什么isPrime自2002年以来没有向JDK添加任何方法.

归档时间：	10 年，10 月前
查看次数：	5756 次
最近记录：	7 年，11 月前