java - 米勒-拉宾测试 : impossible result

Question

我试图在 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);

    }

Answer 1

您有几个表达式使用 == 和 != 比较 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);
}

我想还有更多错误，但这些修复应该会有所帮助。