私は Java で Miller-Rabin 素数性テストを実装し、その計算時間をBigIntegerクラスのネイティブな素数性テストと対峙させようとしていました。私がここにいることを考えると、おそらく私のコードが機能しないと推測したでしょう。問題は、私が得たエラーが、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;
}
編集: 次の行は methodlog(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);
}