static boolean millerRabinPrimeTest()

in commons-numbers-primes/src/main/java/org/apache/commons/numbers/primes/SmallPrimes.java [245:283]

37 lines of code
11 McCabe index (conditional complexity)


    static boolean millerRabinPrimeTest(final int n) {
        final int nMinus1 = n - 1;
        final int s = Integer.numberOfTrailingZeros(nMinus1);
        final int r = nMinus1 >> s;
        // r must be odd, it is not checked here
        int t = 1;
        if (n >= 2047) {
            t = 2;
        }
        if (n >= 1373653) {
            t = 3;
        }
        if (n >= 25326001) {
            t = 4;
        } // works up to 3.2 billion, int range stops at 2.7 so we are safe :-)
        final BigInteger br = BigInteger.valueOf(r);
        final BigInteger bn = BigInteger.valueOf(n);

        for (int i = 0; i < t; i++) {
            final BigInteger a = BigInteger.valueOf(PRIMES[i]);
            final BigInteger bPow = a.modPow(br, bn);
            int y = bPow.intValue();
            if (1 != y && y != nMinus1) {
                int j = 1;
                while (j <= s - 1 && nMinus1 != y) {
                    final long square = ((long) y) * y;
                    y = (int) (square % n);
                    if (1 == y) {
                        return false;
                    } // definitely composite
                    j++;
                }
                if (nMinus1 != y) {
                    return false;
                } // definitely composite
            }
        }
        return true; // definitely prime
    }