首页 > 代码库 > BigInger isProbablePrime

BigInger isProbablePrime

2024-08-26 12:49:31   220人阅读

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


联系
我们