Miller-Rabin 代码对某些数字运行时间较长。漏洞？
Miller-Rabin code runs for extended period for some numbers. Bug?
我仍然是一个编码新手，本着努力提高我的技能的精神，我正在研究 Miller-Rabin java 程序，该程序似乎在大多数情况下都有效。然而，有一些数字导致程序连续 运行（至少很多分钟）。
一个这样的数字是 371。我知道它的复合数（因为我查过了）。我尝试使用 Miller-Rabin 定理和支持大整数的在线模数计算器计算 371，发现自己做了很多很多计算，所以也许我的代码没问题。我不确定。
我已经非常仔细地检查了我的代码几个小时，没有发现任何与 Miller-Rabin 过程的偏差。
我希望一组新的眼睛（或至少更有经验的眼睛）可能会有所帮助。
编辑：更多信息。
我发现它也未能通过测试 49。由于这个数字更容易手动计算，我在下面展示了我的工作：
n = 49
n-1 = 48
Find values for k and m:
48/2^0 = 48
48/2^1 = 24
48/2^2 = 12
48/2^3 = 6
48/2^4 = 3
49/2^5 = 1.5 ***not an integer, so use k=4***
let a = 2 ( a can be 2<a<(n-1) )
I used 2
(n-1)/2^k = m
48/2^4 = 3 *** m = 3 ***
*** b0 = a^m mod n ***
*** b(n) = [b(n)]^2 mod n
b0 = 2^3 mod 49 = 8
b1 = 8^2 mod 49 = 15
b2 = 15^2 mod 49 = 29
b3 = 29^2 mod 49 = 8
b4 = 8^2 mod 49 = 15
b5 = 15^2 mod 49 = 29
并且不断输出b = 8,15,29,8,15,29。
我有大约 20 个不同的 'a' 值，并且发生相同类型的循环（b 具有不同的值）
我不知道接下来要尝试什么。
谁能帮帮我？
这是我的代码：
/**************************************************
I based my code on this explanation on youtube.
I also compared this explanation to others and found them to be consistent
https://www.youtube.com/watch?v=qfgYfyyBRcY
Example:
is 561 prime?
n = 561
subtract 1 from candidate number = 560
while (answer == int) do
560 / 2^1 = 280
560 / 2^2 = 140
560 / 2^3 = 70
560 / 2^4 = 35
560 / 2^5 = 17.5 xxxxxxx use line above
end while
k = 4; m = 35
choose a =2 or 3 or 4
in this case I chose a = 2
b = a^m mod candidate
while (b != 1 or -1) do
b = a^m mod n
b0 = 2^35 mod 561 = 263 mod 561
b1 = 263^2 mod 561 = 166 mod 561
b2 = 166^2 mod 561 = 67 mod 561
b3 = 67^2 mod 561 = 1 mod 561
end while
NOTE: if bo (and only bo) had been either +1 OR -1,
n would be prime (it was 263, in this example).
BUT for b1, b2, and so on, +1 implies composite, -1 probable prime.
***************************************************/
import java.lang.*;
import java.math.BigInteger;
import java.util.*;
import java.util.concurrent.TimeUnit;
public class myMillerRabin{
// these variables are made global so that their creation has no effect on computation time
public static BigInteger number; // number = (n-1)
public static BigInteger candidate; // number being tested
public static Scanner scan = new Scanner(System.in); // scanner for keyboard input
public static String input; // reads in candidate as string and passes it to BigInteger
public static long endPrimeTest = 0; // timer end
public static long startPrimeTest = 0; // timer start
public static BigInteger testForNegOne; // tests for eg. 2 mod 3 = 2 = -1
public static String _a; // var to hold value for 'a'. Often 2 is used, but 'a'' can be: 1<a<(candidate-1)
public static void main(String[] args){
System.out.println("Enter a candidate number: ");
while(isValidInput() == false){ // wait for valid numerical input
System.out.println("Error: Enter valid input!");
}
if (candidate.longValue() == 2){ // 2 is prime
System.out.println("Two is a prime number.");
}
else if(candidate.longValue() % 2 == 0){ // evens are not prime
System.out.println("Number is even, thus it is NOT prime! ");
}
else{
isProbablePrime(candidate); // run the test
System.out.println("Time taken : " + (endPrimeTest - startPrimeTest) + " nanoseconds");
}
} ////////////end main method
public static boolean isProbablePrime(BigInteger x){
boolean test1, test2, test3;
int twoToK = 0x0001; // 2^0 = 1
BigInteger two = new BigInteger("2");
long testCand = x.longValue();
BigInteger aExp, b, modTest;
number = x.subtract(BigInteger.ONE);
System.out.println("n - 1: " + number); // used for testing
System.out.println("candidate as bigint: " + candidate.intValue()); // used for testing
System.out.println("Enter an iterator: 2 is usually fine...");
_a = scan.next();
BigInteger a = new BigInteger(_a);
int k = 0;
BigInteger m;
int _m = 0;
startPrimeTest = System.nanoTime(); // start timer
// this increases the powers of 2 (starting with 2^0)that are divided by
// to obtain the values of k and m
while((number.intValue() % twoToK)== 0){
_m = number.intValue() / twoToK;
System.out.println("Value of m: " + number.intValue() / twoToK);
System.out.println("twoToK : "+ twoToK);
twoToK = twoToK << 1; // Bitshift left to increase power of 2
k++; // this final value of will be one more than the one we want
}
k--; // obtain value of k
System.out.println("k = " + k); // used for testing
System.out.println("m = " + _m); // used for testing
String mString = String.valueOf(_m);
m = new BigInteger(mString);
aExp = a.pow(k);
System.out.println("a: " + a + " k: " + k ); // used for testing
System.out.println("twoExp: "+ aExp); // used for testing
b = a.modPow(m,candidate);
System.out.println("b= "+ b + " mod " + candidate.intValue()); // used for testing
// tests for a congruence of -1 eg: 2mod3 = 2 = -1
testForNegOne = candidate.subtract(b);
System.out.println("Test for neg one: " + testForNegOne.intValue()); // used for testing
// if initial test is 1 OR -1, then prime
test1 = b.equals(BigInteger.ONE);
test2 = b.equals(BigInteger.ONE.negate());
// test for: a^m mod candidate (congruent to) -1
test3 = testForNegOne.equals(BigInteger.ONE);
System.out.println("Test for +1 initial test: "+test1); // used for testing
System.out.println("Test for -1 initial test: "+test2); // used for testing
System.out.println("Test for -1 Congruence: " + test3); // used for testing
// if test1, 2, or 3 return true for b0, then candidate is a probable prime
if(test1 == true || test2 == true || test3 == true){
System.out.println("Candidate is probable prime");
endPrimeTest = System.nanoTime();
return true;
}
else{ // otherwise keep testing
while(!test1 && !test2 && !test3){
b = b.modPow(two, candidate);
modTest = candidate.subtract(b);
System.out.println("b = " + b + ", -" + modTest);
test3 = modTest.equals(BigInteger.ONE);
test1 = b.equals(BigInteger.ONE); // is b == 1
test2 = b.negate().equals(BigInteger.ONE); // is b== -1
System.out.println("TEst 1: "+ test1);
System.out.println("TEst 2:" + test2);
System.out.println("Test 3:" + test3);
System.out.println("B: " + b );
// sleep used for testing purposes
/*
try {
Thread.sleep(1000);
}
catch(InterruptedException ex) {
Thread.currentThread().interrupt();
}
*/
}
if (test1){ // if bn = 1, then the number is composite
System.out.println("Implied Composite");
endPrimeTest = System.nanoTime();
return false;
}
else{ // if test2 or test3 are true, then candidate is a probable prime
System.out.println("Probably Prime");
System.out.println("b= "+ b.intValue());
endPrimeTest = System.nanoTime();
return true;
}
}
}
// Method to check input to see if it is a valid integer input
public static boolean isValidInput(){
try{
input = scan.next();
candidate = new BigInteger(input);
}
catch (NumberFormatException exception){
//System.out.println("Bad input detected"); // used for debugging
return false;
}
return true;
} // end isValidInput method
}
根据 Fermat's little theorem 如果 p 是素数，我们必须有 a^(p-1) 等于 1 modulo p。因此，如果我们写 p-1 = s * 2^k，s 为奇数，然后计算 a^s，然后重复对结果进行平方，如果 p 是素数，我们必须在最多 k 次平方后得到 1。
此外，我们可以测试最后一个不同于1的结果。对于素数p，它必须与-1 mod p全等。如果是其他情况，我们不仅知道 p 不是质数，而且我们甚至发现了 p 的一个非平凡因子（我写 == 表示全等 mod p）：
x^2 == 1
x^2 - 1 == 0
(x + 1) * (x - 1) == 0
现在，由于 (x + 1) 和 (x - 1) 都不能被 p 整除，但它们的乘积可以整除，因此 p 的一个非平凡因子是 gcd(p, x+1)。
我仍然是一个编码新手，本着努力提高我的技能的精神，我正在研究 Miller-Rabin java 程序，该程序似乎在大多数情况下都有效。然而，有一些数字导致程序连续 运行（至少很多分钟）。
一个这样的数字是 371。我知道它的复合数（因为我查过了）。我尝试使用 Miller-Rabin 定理和支持大整数的在线模数计算器计算 371，发现自己做了很多很多计算，所以也许我的代码没问题。我不确定。
我已经非常仔细地检查了我的代码几个小时，没有发现任何与 Miller-Rabin 过程的偏差。
我希望一组新的眼睛（或至少更有经验的眼睛）可能会有所帮助。
编辑：更多信息。 我发现它也未能通过测试 49。由于这个数字更容易手动计算，我在下面展示了我的工作：
n = 49
n-1 = 48
Find values for k and m:
48/2^0 = 48
48/2^1 = 24
48/2^2 = 12
48/2^3 = 6
48/2^4 = 3
49/2^5 = 1.5 ***not an integer, so use k=4***
let a = 2 ( a can be 2<a<(n-1) )
I used 2
(n-1)/2^k = m
48/2^4 = 3 *** m = 3 ***
*** b0 = a^m mod n ***
*** b(n) = [b(n)]^2 mod n
b0 = 2^3 mod 49 = 8
b1 = 8^2 mod 49 = 15
b2 = 15^2 mod 49 = 29
b3 = 29^2 mod 49 = 8
b4 = 8^2 mod 49 = 15
b5 = 15^2 mod 49 = 29
并且不断输出b = 8,15,29,8,15,29。 我有大约 20 个不同的 'a' 值，并且发生相同类型的循环（b 具有不同的值）
我不知道接下来要尝试什么。 谁能帮帮我？
这是我的代码：
/**************************************************
I based my code on this explanation on youtube.
I also compared this explanation to others and found them to be consistent
https://www.youtube.com/watch?v=qfgYfyyBRcY
Example:
is 561 prime?
n = 561
subtract 1 from candidate number = 560
while (answer == int) do
560 / 2^1 = 280
560 / 2^2 = 140
560 / 2^3 = 70
560 / 2^4 = 35
560 / 2^5 = 17.5 xxxxxxx use line above
end while
k = 4; m = 35
choose a =2 or 3 or 4
in this case I chose a = 2
b = a^m mod candidate
while (b != 1 or -1) do
b = a^m mod n
b0 = 2^35 mod 561 = 263 mod 561
b1 = 263^2 mod 561 = 166 mod 561
b2 = 166^2 mod 561 = 67 mod 561
b3 = 67^2 mod 561 = 1 mod 561
end while
NOTE: if bo (and only bo) had been either +1 OR -1,
n would be prime (it was 263, in this example).
BUT for b1, b2, and so on, +1 implies composite, -1 probable prime.
***************************************************/
import java.lang.*;
import java.math.BigInteger;
import java.util.*;
import java.util.concurrent.TimeUnit;
public class myMillerRabin{
// these variables are made global so that their creation has no effect on computation time
public static BigInteger number; // number = (n-1)
public static BigInteger candidate; // number being tested
public static Scanner scan = new Scanner(System.in); // scanner for keyboard input
public static String input; // reads in candidate as string and passes it to BigInteger
public static long endPrimeTest = 0; // timer end
public static long startPrimeTest = 0; // timer start
public static BigInteger testForNegOne; // tests for eg. 2 mod 3 = 2 = -1
public static String _a; // var to hold value for 'a'. Often 2 is used, but 'a'' can be: 1<a<(candidate-1)
public static void main(String[] args){
System.out.println("Enter a candidate number: ");
while(isValidInput() == false){ // wait for valid numerical input
System.out.println("Error: Enter valid input!");
}
if (candidate.longValue() == 2){ // 2 is prime
System.out.println("Two is a prime number.");
}
else if(candidate.longValue() % 2 == 0){ // evens are not prime
System.out.println("Number is even, thus it is NOT prime! ");
}
else{
isProbablePrime(candidate); // run the test
System.out.println("Time taken : " + (endPrimeTest - startPrimeTest) + " nanoseconds");
}
} ////////////end main method
public static boolean isProbablePrime(BigInteger x){
boolean test1, test2, test3;
int twoToK = 0x0001; // 2^0 = 1
BigInteger two = new BigInteger("2");
long testCand = x.longValue();
BigInteger aExp, b, modTest;
number = x.subtract(BigInteger.ONE);
System.out.println("n - 1: " + number); // used for testing
System.out.println("candidate as bigint: " + candidate.intValue()); // used for testing
System.out.println("Enter an iterator: 2 is usually fine...");
_a = scan.next();
BigInteger a = new BigInteger(_a);
int k = 0;
BigInteger m;
int _m = 0;
startPrimeTest = System.nanoTime(); // start timer
// this increases the powers of 2 (starting with 2^0)that are divided by
// to obtain the values of k and m
while((number.intValue() % twoToK)== 0){
_m = number.intValue() / twoToK;
System.out.println("Value of m: " + number.intValue() / twoToK);
System.out.println("twoToK : "+ twoToK);
twoToK = twoToK << 1; // Bitshift left to increase power of 2
k++; // this final value of will be one more than the one we want
}
k--; // obtain value of k
System.out.println("k = " + k); // used for testing
System.out.println("m = " + _m); // used for testing
String mString = String.valueOf(_m);
m = new BigInteger(mString);
aExp = a.pow(k);
System.out.println("a: " + a + " k: " + k ); // used for testing
System.out.println("twoExp: "+ aExp); // used for testing
b = a.modPow(m,candidate);
System.out.println("b= "+ b + " mod " + candidate.intValue()); // used for testing
// tests for a congruence of -1 eg: 2mod3 = 2 = -1
testForNegOne = candidate.subtract(b);
System.out.println("Test for neg one: " + testForNegOne.intValue()); // used for testing
// if initial test is 1 OR -1, then prime
test1 = b.equals(BigInteger.ONE);
test2 = b.equals(BigInteger.ONE.negate());
// test for: a^m mod candidate (congruent to) -1
test3 = testForNegOne.equals(BigInteger.ONE);
System.out.println("Test for +1 initial test: "+test1); // used for testing
System.out.println("Test for -1 initial test: "+test2); // used for testing
System.out.println("Test for -1 Congruence: " + test3); // used for testing
// if test1, 2, or 3 return true for b0, then candidate is a probable prime
if(test1 == true || test2 == true || test3 == true){
System.out.println("Candidate is probable prime");
endPrimeTest = System.nanoTime();
return true;
}
else{ // otherwise keep testing
while(!test1 && !test2 && !test3){
b = b.modPow(two, candidate);
modTest = candidate.subtract(b);
System.out.println("b = " + b + ", -" + modTest);
test3 = modTest.equals(BigInteger.ONE);
test1 = b.equals(BigInteger.ONE); // is b == 1
test2 = b.negate().equals(BigInteger.ONE); // is b== -1
System.out.println("TEst 1: "+ test1);
System.out.println("TEst 2:" + test2);
System.out.println("Test 3:" + test3);
System.out.println("B: " + b );
// sleep used for testing purposes
/*
try {
Thread.sleep(1000);
}
catch(InterruptedException ex) {
Thread.currentThread().interrupt();
}
*/
}
if (test1){ // if bn = 1, then the number is composite
System.out.println("Implied Composite");
endPrimeTest = System.nanoTime();
return false;
}
else{ // if test2 or test3 are true, then candidate is a probable prime
System.out.println("Probably Prime");
System.out.println("b= "+ b.intValue());
endPrimeTest = System.nanoTime();
return true;
}
}
}
// Method to check input to see if it is a valid integer input
public static boolean isValidInput(){
try{
input = scan.next();
candidate = new BigInteger(input);
}
catch (NumberFormatException exception){
//System.out.println("Bad input detected"); // used for debugging
return false;
}
return true;
} // end isValidInput method
}
根据 Fermat's little theorem 如果 p 是素数，我们必须有 a^(p-1) 等于 1 modulo p。因此，如果我们写 p-1 = s * 2^k，s 为奇数，然后计算 a^s，然后重复对结果进行平方，如果 p 是素数，我们必须在最多 k 次平方后得到 1。
此外，我们可以测试最后一个不同于1的结果。对于素数p，它必须与-1 mod p全等。如果是其他情况，我们不仅知道 p 不是质数，而且我们甚至发现了 p 的一个非平凡因子（我写 == 表示全等 mod p）：
x^2 == 1
x^2 - 1 == 0
(x + 1) * (x - 1) == 0
现在，由于 (x + 1) 和 (x - 1) 都不能被 p 整除，但它们的乘积可以整除，因此 p 的一个非平凡因子是 gcd(p, x+1)。