java - Miller-Rabin 代码对于某些数字运行时间较长。漏洞？

Question

我仍然是一个新手编码员，本着努力提高我的技能的精神，我正在开发一个 Miller-Rabin java 程序，该程序似乎在大多数情况下都能工作。然而，有一些数字会导致程序连续运行(至少几分钟)。

其中一个数字是 371。我知道它的合数(因为我查过)。我尝试使用米勒-拉宾定理和支持大整数的在线模数计算器来计算 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   


}

Answer 1

根据Fermat's little theorem如果 p 是素数，则 a^(p-1) 必须等于 1 模 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 整除，所以 p 的一个重要因子是 gcd(p, x+1)。