我试图在 Java 上实现 Miller-Rabin 素数测试，并将其计算时间与 BigInteger 类的 native 素数测试进行比较。鉴于我在这里，您可能已经猜到我的代码不起作用。问题是，我得到的错误是 Lady Math 所说的不可能的错误。我想知道我做错了什么。
Miller-Rabin 素数测试背后的想法，无需太多数学知识，就是所有素数都满足某种规律。如果不满足该礼节，则该数字是复合的；但是，如果满足该性质，则该数可能 是素数，或者它可能属于称为伪素数 的合数的子集。绝对不能发生的是素数被测试识别为合数。
这正是运行我的代码时有时会发生的情况。
我在我的代码中搜索了数学错误，我认为没有。我尝试搜索 Java 错误，但没有找到。显然有些东西(或很多)我没有看到，所以我想寻求帮助。
下面是一个静态类的main，它只是为了容纳Miller-Rabin 测试的实现而创建的，它出现在main 之后。它不是概率测试，而是确定性测试:该方法搜索所有可能的证人，如果找到一个，则返回 false(即不是质数)；否则返回 true。
public static void main(String[] args) {
long start;
Random random = new Random();
int N = Integer.parseInt("10");
BigInteger a,b,c,d;
long stopMR, stopNative;
boolean answerMR, answerNative;
for(int i=0 ; i<6 ; i++, N*=3)
{
a = new BigInteger(N, random);
System.out.printf("\tTEST %d\n\nThe number to be checked is: \n\t %s\n" +
// "Written in 2-base: \n\t %s\n" +
"Number of bits of a: %d \n", i,
a.toString(),
// a.toString(2),
a.toString(2).length());
start = System.nanoTime();
answerMR = primalityTest_MillerRabin(a);
stopMR = System.nanoTime();
stopMR -= start;
start = System.nanoTime();
answerNative = a.isProbablePrime(40);
stopNative = System.nanoTime();
stopNative -= start;
System.out.printf("The test of Miller-Rabin said that the number %s.\n"
+ "The native test said that the number %s.\n"
+ "The time of MR is %d.\n"
+ "The time of the native is %d.\n"
+ "The difference Time(MR)-Time(native) is %d.\n",
answerMR ? "is prime" : "isn't prime" ,
answerNative ? "is prime" : "isn't prime" ,
stopMR, stopNative, stopMR - stopNative
);
a = BigInteger.probablePrime(N, random);
System.out.printf("\tTEST %d\n\nThe number to be checked is: \n\t %s\n" +
// "Written in 2-base: \n\t %s\n" +
"Number of bits of a: %d \n", i,
a.toString(),
// a.toString(2),
a.toString(2).length());
start = System.nanoTime();
answerMR = primalityTest_MillerRabin(a);
stopMR = System.nanoTime();
stopMR -= start;
start = System.nanoTime();
answerNative = a.isProbablePrime(40);
stopNative = System.nanoTime();
stopNative -= start;
System.out.printf("The test of Miller-Rabin said that the number %s.\n"
+ "The native test said that the number %s.\n"
+ "The time of MR is %d.\n"
+ "The time of the native is %d.\n"
+ "The difference Time(MR)-Time(native) is %d.\n=====\n",
answerMR ? "is prime" : "isn't prime" ,
answerNative ? "is prime" : "isn't prime" ,
stopMR, stopNative, stopMR - stopNative
);
}
}
/** Tests {@code n} for primality using the <i>Miller-Rabin algorithm</i>.
*
* <p><br> For {@code n} minor than <b>3,825,123,056,546,413,051</b> (i.e. roughtly four millions of millions of millions,
* i.e. 4·10<sup>18</sup>) the test is deterministic and have time complexity of Θ<font size=+1>(</font>10·modPow(·,n)<font size=+1>)</font>.
* <br> For {@code n} greater than <b>3,825,123,056,546,413,051</b> the test is deterministic and have time complexity of
* Θ<font size=+1>(</font>2·log<sub>2</sub><sup>2</sup>(n)·modPow(·,n)<font size=+1>)</font>.
*
* @param n
* @return
*/
public static boolean primalityTest_MillerRabin(BigInteger n){
// If n is divided by 2 or is less than 2, then n is not prime.
if( n.intValue()%2== 0 || n.equals(TWO) )
{
System.out.printf("The number is even.\n");
return false;
}
// n = d*2^s +1
BigInteger pMinus1 = n.subtract(ONE);
int s = 0;
while (pMinus1.mod(TWO).equals(ZERO))
{
s++;
pMinus1 = pMinus1.divide(TWO);
}
BigInteger d = pMinus1;
System.out.printf("%s is %s*2^%d+1.\n", n.toString(), d.toString(),s);
// Old code:
// pMinus1.divide(BigInteger.valueOf(2L << r - 1));
// For some n is known what witness one has to choose in order to verify is n is composite.
// While the code for EVERY known limit is shown, only those not-redundant is not comment.
if(n.compareTo(LIMIT_2047)<0)
return ! isTWOWitnessOfCompositenessOfN_MR( n, d, s) ;
if(n.compareTo(LIMIT_9080191)<0)
return ! (
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(31) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(73) , n, d, s) );
if(n.compareTo(LIMIT_4759123141)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(7) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(61) , n, d, s) );
if(n.compareTo(LIMIT_1122004669633)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(13) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(23) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(1662803) , n, d, s) );
if(n.compareTo(LIMIT_2152302898747)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(3) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(5) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(7) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(11) , n, d, s) );
if(n.compareTo(LIMIT_3474749660383)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(3) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(5) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(7) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(11) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(13) , n, d, s) );
if(n.compareTo(LIMIT_341550071728321)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(3) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(5) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(7) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(11) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(13) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(17) , n, d, s) );
if(n.compareTo(LIMIT_3825123056546413051)<0)
return ! (
isTWOWitnessOfCompositenessOfN_MR( n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(3) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(5) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(7) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(11) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(13) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(17) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(19) , n, d, s) ||
isAWitnessOfCompositenessOfN_MR( BigInteger.valueOf(23) , n, d, s) );
// ...otherwise the program does an exaustive search for witness
System.out.printf("The Miller-Rabin Test has no shortcuts.\n");
boolean witnessFound = false;
int logn = (int) log(n,2) +1;
BigInteger limit = ( n.subtract(ONE) ).min( BigInteger.valueOf(2*logn*logn) );
for(BigInteger a = TWO ; witnessFound && a.compareTo(limit)<=0 ; a.add(ONE))
witnessFound = isAWitnessOfCompositenessOfN_MR( a , n, d, s);
return !witnessFound;
}
/** Return {@code true} if and only if {@code a} is a witness for the compositeness of {@code n}, i.e. if and only if:
* <ol> n = d·2<sup>s</sup> + 1 <br>
* gcd(a,n) = 1 (i.e. a doesn't divide n) <br>
* _<br>
* a<sup>d</sup> ≠ 1 (mod n) <br>
* a<sup>(d·2^r)</sup> ≠ -1 (mod n) for all rϵ[0,s) </ol>
*
* If the method returns {@code true} then {@code n} is definitely a composite number. However if the method returns {@code false} it
* still may be possible for {@code n} to be composite.
*
* <p>If this method recognize {@code a} as a witness for the compositeness of {@code n}
*
* @param a
* @param n
* @param d
* @param s
* @return
*/
public static boolean isAWitnessOfCompositenessOfN_MR(BigInteger a, BigInteger n, BigInteger d, int s){
System.out.printf("\t Verifying if %s is a witness of the compositness of %s.\n", a.toString(), n.toString());
if( a.gcd(n) == ONE )
{
BigInteger dMultiplyTwoPowR = a.modPow(d, n),
nMinusOne = NEGATIVE_ONE.mod(n);
boolean answer = dMultiplyTwoPowR != ONE;
for(int r=1 ; answer && r<s ; r++)
{
System.out.printf("\t\t Testing r=%d.\n", r);
answer = answer &&
dMultiplyTwoPowR.modPow(TWO, n) != nMinusOne;
}
System.out.printf("\t The number %s %s a witness of the compositness of %s.\n", a.toString(), answer ? "is" : "isn't", n.toString());
return answer;
}
else
{
System.out.printf("\t %s divides %s.\n", a.toString(), n.toString());
return true;
}
}
/** Returns {@code isAWitnessOfCompositenessOfN_MR(TWO, n, d, s)}.
*
* <p><u><b>Warning:</b></u> This method avoids to control if gcd(2, {@code n})=1.
*
* @param n
* @param d
* @param s
* @return
*/
public static boolean isTWOWitnessOfCompositenessOfN_MR( BigInteger n, BigInteger d, int s){
System.out.printf("\t Verifying if 2 is a witness of the compositness of %s.\n", n.toString());
BigInteger dMultiplyTwoPowR = TWO.modPow(d, n),
nMinusOne = NEGATIVE_ONE.mod(n);
boolean answer = dMultiplyTwoPowR != ONE;
for(int r=1 ; answer && r<s ; r++)
{
System.out.printf("\t\t Testing r=%d.\n", r);
answer = answer &&
dMultiplyTwoPowR.modPow(TWO, n) != nMinusOne;
}
System.out.printf("\t The number 2 %s a witness of the compositness of %s.\n", answer ? "is" : "isn't", n.toString());
return answer;
}
编辑:下面几行是方法log(x,base)。
/** Returns the logarithm of a number {@code x} in the selected {@code base}.
* <p>
* <b>Time Complexity:</b> Θ(1). <br>
* <b>Space Complexity:</b> Θ(log<sub>10</sub>(x)). <br>
*
* @param x
* @param base
* @return
*/
public static double log(BigInteger x, float base){
String support = x.toString();
int n = support.length();
double log10 = n + Float.parseFloat("0."+support);
if(base==10) return log10;
else return log10 / Math.log10(base);
}
最佳答案
您有几个表达式使用 == 和 != 比较 BigInteger 对象。这必须替换为对 equals 的调用，否定 != 的结果。
此外，我认为 isAWitnessOfCompositenessOfN_MR 中存在复制粘贴错误:
! dMultiplyTwoPowR.modPow(TWO, n).equals( nMinusOne );
我认为 TWO 应该用 a 代替。
编辑 日志中的错误。使用以下代码:
public static double log(BigInteger x, base b){
String support = x.toString();
int n = support.length();
double log10 = n + Math.log10( Double.parseDouble("0."+support) );
return log10/Math.log10(b);
}
我想还有更多错误，但这些修复应该会有所帮助。
关于java - 米勒-拉宾测试 : impossible result，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32404536/