首页 > 代码库 > BigInger isProbablePrime
BigInger isProbablePrime
JAVA BigInteger 成员函数： isProbablePrime
public boolean isProbablePrime(int certainty)
如果此 BigInteger 可能为素数，则返回 true，如果它一定为合数，则返回 false。如果 certainty <= 0，则返回 true。
参数：
certainty - 调用方允许的不确定性的度量。如果该调用返回 true，则此 BigInteger 是素数的概率超出 (1 - 1/2certainty)。此方法的执行时间与此参数的值是成比例的。
返回：
如果此 BigInteger 可能为素数，则返回 true，如果它一定为合数，则返回 false。
java中的isProbablePrime函数是针对BigInteger类的一个素数判断函数，它的实现原理其实并不复杂，只是要分许多情况讨论，要用到Miller-Rabin素数测试和Lucas-Lehmer测试，它是一个概率算法，返回的结果：一个数不是素数或者一个数可能是素数。下面只给出它在jdk1.6 src中的主要源代码：
public boolean isProbablePrime(int certainty) { if (certainty <= 0) return true; BigInteger w = this.abs(); if (w.equals(TWO)) return true; if (!w.testBit(0) || w.equals(ONE)) return false; return w.primeToCertainty(certainty, null); } public boolean testBit(int n) { if (n < 0) throw new ArithmeticException("Negative bit address"); return (getInt(n >>> 5) & (1 << (n & 31))) != 0; } private int getInt(int n) { if (n < 0) return 0; if (n >= mag.length) return signInt(); int magInt = mag[mag.length-n-1]; return (signum >= 0 ? magInt : (n <= firstNonzeroIntNum() ? -magInt : ~magInt)); } boolean primeToCertainty(int certainty, Random random) { int rounds = 0; int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2; // The relationship between the certainty and the number of rounds // we perform is given in the draft standard ANSI X9.80, "PRIME // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES". int sizeInBits = this.bitLength(); if (sizeInBits < 100) { rounds = 50; rounds = n < rounds ? n : rounds; return passesMillerRabin(rounds, random); } if (sizeInBits < 256) { rounds = 27; } else if (sizeInBits < 512) { rounds = 15; } else if (sizeInBits < 768) { rounds = 8; } else if (sizeInBits < 1024) { rounds = 4; } else { rounds = 2; } rounds = n < rounds ? n : rounds; return passesMillerRabin(rounds, random) && passesLucasLehmer(); }
BigInger isProbablePrime
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。