/*
* Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
/*
* @test
* @library /lib/testlibrary/
* @build jdk.testlibrary.*
* @run main PrimeTest
* @bug 8026236 8074460 8078672
* @summary test primality verification methods in BigInteger (use -Dseed=X to set PRNG seed)
* @author bpb
* @key randomness
*/
import java.math.BigInteger;
import java.util.BitSet;
import java.util.List;
import java.util.NavigableSet;
import java.util.Set;
import java.util.SplittableRandom;
import java.util.TreeSet;
import jdk.testlibrary.RandomFactory;
import static java.util.stream.Collectors.toCollection;
import static java.util.stream.Collectors.toList;
public class PrimeTest {
private static final int DEFAULT_UPPER_BOUND = 1299709; // 100000th prime
private static final int DEFAULT_CERTAINTY = 100;
private static final int NUM_NON_PRIMES = 10000;
/**
* Run the test.
*
* @param args The parameters.
* @throws Exception on failure
*/
public static void main(String[] args) throws Exception {
// Prepare arguments
int upperBound = args.length > 0 ? Integer.valueOf(args[0]) : DEFAULT_UPPER_BOUND;
int certainty = args.length > 1 ? Integer.valueOf(args[1]) : DEFAULT_CERTAINTY;
boolean parallel = args.length > 2 ? Boolean.valueOf(args[2]) : true;
// Echo parameter settings
System.out.println("Upper bound = " + upperBound
+ "\nCertainty = " + certainty
+ "\nParallel = " + parallel);
// Get primes through specified bound (inclusive) and Integer.MAX_VALUE
NavigableSet<BigInteger> primes = getPrimes(upperBound);
// Check whether known primes are identified as such
boolean primeTest = checkPrime(primes, certainty, parallel);
System.out.println("Prime test result: " + (primeTest ? "SUCCESS" : "FAILURE"));
if (!primeTest) {
System.err.println("Prime test failed");
}
// Check whether known non-primes are not identified as primes
boolean nonPrimeTest = checkNonPrime(primes, certainty);
System.out.println("Non-prime test result: " + (nonPrimeTest ? "SUCCESS" : "FAILURE"));
boolean mersennePrimeTest = checkMersennePrimes(certainty);
System.out.println("Mersenne test result: " + (mersennePrimeTest ? "SUCCESS" : "FAILURE"));
if (!primeTest || !nonPrimeTest || !mersennePrimeTest) {
throw new Exception("PrimeTest FAILED!");
}
System.out.println("PrimeTest succeeded!");
}
/**
* Create a {@code BitSet} wherein a set bit indicates the corresponding
* index plus 2 is prime. That is, if bit N is set, then the integer N + 2
* is prime. The values 0 and 1 are intentionally excluded. See the
* <a
* href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_description">
* Sieve of Eratosthenes</a> algorithm description for more information.
*
* @param upperBound The maximum prime to allow
* @return bits indicating which indexes represent primes
*/
private static BitSet createPrimes(int upperBound) {
int nbits = upperBound - 1;
BitSet bs = new BitSet(nbits);
for (int p = 2; p * p < upperBound;) {
for (int i = p * p; i < nbits + 2; i += p) {
bs.set(i - 2, true);
}
do {
++p;
} while (p > 1 && bs.get(p - 2));
}
bs.flip(0, nbits);
return bs;
}
/**
* Load the primes up to the specified bound (inclusive) into a
* {@code NavigableSet}, appending the prime {@code Integer.MAX_VALUE}.
*
* @param upperBound The maximum prime to allow
* @return a set of primes
*/
private static NavigableSet<BigInteger> getPrimes(int upperBound) {
BitSet bs = createPrimes(upperBound);
NavigableSet<BigInteger> primes = bs.stream()
.mapToObj(p -> BigInteger.valueOf(p + 2))
.collect(toCollection(TreeSet::new));
primes.add(BigInteger.valueOf(Integer.MAX_VALUE));
System.out.println(String.format("Created %d primes", primes.size()));
return primes;
}
/**
* Verifies whether the fraction of probable primes detected is at least 1 -
* 1/2^certainty.
*
* @return true if and only if the test succeeds
*/
private static boolean checkPrime(Set<BigInteger> primes,
int certainty,
boolean parallel) {
long probablePrimes = (parallel ? primes.parallelStream() : primes.stream())
.filter(bi -> bi.isProbablePrime(certainty))
.count();
// N = certainty / 2
// Success if p/t >= 1 - 1/4^N
// or (p/t)*4^N >= 4^N - 1
// or p*4^N >= t*(4^N - 1)
BigInteger p = BigInteger.valueOf(probablePrimes);
BigInteger t = BigInteger.valueOf(primes.size());
BigInteger fourToTheC = BigInteger.valueOf(4).pow(certainty / 2);
BigInteger fourToTheCMinusOne = fourToTheC.subtract(BigInteger.ONE);
BigInteger left = p.multiply(fourToTheC);
BigInteger right = t.multiply(fourToTheCMinusOne);
if (left.compareTo(right) < 0) {
System.err.println("Probable prime certainty test failed");
}
return left.compareTo(right) >= 0;
}
/**
* Verifies whether all {@code BigInteger}s in the tested range for which
* {@code isProbablePrime()} returns {@code false} are <i>not</i>
* prime numbers.
*
* @return true if and only if the test succeeds
*/
private static boolean checkNonPrime(NavigableSet<BigInteger> primes,
int certainty) {
int maxPrime = DEFAULT_UPPER_BOUND;
try {
maxPrime = primes.last().intValueExact();
} catch (ArithmeticException e) {
// ignore it
}
// Create a list of non-prime BigIntegers.
SplittableRandom splitRandom = RandomFactory.getSplittableRandom();
List<BigInteger> nonPrimeBigInts = (splitRandom)
.ints(NUM_NON_PRIMES, 2, maxPrime).mapToObj(BigInteger::valueOf)
.filter(b -> !b.isProbablePrime(certainty)).collect(toList());
// If there are any non-probable primes also in the primes list then fail.
boolean failed = nonPrimeBigInts.stream().anyMatch(primes::contains);
// In the event, print which purported non-primes were actually prime.
if (failed) {
for (BigInteger bigInt : nonPrimeBigInts) {
if (primes.contains(bigInt)) {
System.err.println("Prime value thought to be non-prime: " + bigInt);
}
}
}
return !failed;
}
/**
* Verifies whether a specified subset of Mersenne primes are correctly
* identified as being prime. See
* <a href="https://en.wikipedia.org/wiki/Mersenne_prime">Mersenne prime</a>
* for more information.
*
* @return true if and only if the test succeeds
*/
private static boolean checkMersennePrimes(int certainty) {
int[] MERSENNE_EXPONENTS = {
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203,
2281, 3217, 4253, // uncomment remaining array elements to make this test run a long time
/* 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497,
86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269,
2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951,
30402457, 32582657, 37156667, 42643801, 43112609, 57885161 */
};
System.out.println("Checking first "+MERSENNE_EXPONENTS.length+" Mersenne primes");
boolean result = true;
for (int n : MERSENNE_EXPONENTS) {
BigInteger mp = BigInteger.ONE.shiftLeft(n).subtract(BigInteger.ONE);
if (!mp.isProbablePrime(certainty)) {
System.err.println("Mp with p = "+n+" not classified as prime");
result = false;
}
}
return result;
}
}