1 /*
   2  * Copyright (c) 2014, 2017, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 /*
  27  * @test
  28  * @library /test/lib
  29  * @build jdk.test.lib.RandomFactory
  30  * @run main PrimeTest
  31  * @bug 8026236 8074460 8078672
  32  * @summary test primality verification methods in BigInteger (use -Dseed=X to set PRNG seed)
  33  * @author bpb
  34  * @key randomness
  35  */
  36 import java.math.BigInteger;
  37 import java.util.BitSet;
  38 import java.util.List;
  39 import java.util.NavigableSet;
  40 import java.util.Set;
  41 import java.util.SplittableRandom;
  42 import java.util.TreeSet;
  43 import jdk.test.lib.RandomFactory;
  44 import static java.util.stream.Collectors.toCollection;
  45 import static java.util.stream.Collectors.toList;
  46 
  47 public class PrimeTest {
  48 
  49     private static final int DEFAULT_UPPER_BOUND = 1299709; // 100000th prime
  50     private static final int DEFAULT_CERTAINTY = 100;
  51     private static final int NUM_NON_PRIMES = 10000;
  52 
  53     /**
  54      * Run the test.
  55      *
  56      * @param args The parameters.
  57      * @throws Exception on failure
  58      */
  59     public static void main(String[] args) throws Exception {
  60         // Prepare arguments
  61         int upperBound = args.length > 0 ? Integer.valueOf(args[0]) : DEFAULT_UPPER_BOUND;
  62         int certainty = args.length > 1 ? Integer.valueOf(args[1]) : DEFAULT_CERTAINTY;
  63         boolean parallel = args.length > 2 ? Boolean.valueOf(args[2]) : true;
  64 
  65         // Echo parameter settings
  66         System.out.println("Upper bound = " + upperBound
  67                 + "\nCertainty = " + certainty
  68                 + "\nParallel = " + parallel);
  69 
  70         // Get primes through specified bound (inclusive) and Integer.MAX_VALUE
  71         NavigableSet<BigInteger> primes = getPrimes(upperBound);
  72 
  73         // Check whether known primes are identified as such
  74         boolean primeTest = checkPrime(primes, certainty, parallel);
  75         System.out.println("Prime test result: " + (primeTest ? "SUCCESS" : "FAILURE"));
  76         if (!primeTest) {
  77             System.err.println("Prime test failed");
  78         }
  79 
  80         // Check whether known non-primes are not identified as primes
  81         boolean nonPrimeTest = checkNonPrime(primes, certainty);
  82         System.out.println("Non-prime test result: " + (nonPrimeTest ? "SUCCESS" : "FAILURE"));
  83 
  84         boolean mersennePrimeTest = checkMersennePrimes(certainty);
  85         System.out.println("Mersenne test result: " + (mersennePrimeTest ? "SUCCESS" : "FAILURE"));
  86 
  87         if (!primeTest || !nonPrimeTest || !mersennePrimeTest) {
  88             throw new Exception("PrimeTest FAILED!");
  89         }
  90 
  91         System.out.println("PrimeTest succeeded!");
  92     }
  93 
  94     /**
  95      * Create a {@code BitSet} wherein a set bit indicates the corresponding
  96      * index plus 2 is prime. That is, if bit N is set, then the integer N + 2
  97      * is prime. The values 0 and 1 are intentionally excluded. See the
  98      * <a
  99      * href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_description">
 100      * Sieve of Eratosthenes</a> algorithm description for more information.
 101      *
 102      * @param upperBound The maximum prime to allow
 103      * @return bits indicating which indexes represent primes
 104      */
 105     private static BitSet createPrimes(int upperBound) {
 106         int nbits = upperBound - 1;
 107         BitSet bs = new BitSet(nbits);
 108         for (int p = 2; p * p < upperBound;) {
 109             for (int i = p * p; i < nbits + 2; i += p) {
 110                 bs.set(i - 2, true);
 111             }
 112             do {
 113                 ++p;
 114             } while (p > 1 && bs.get(p - 2));
 115         }
 116         bs.flip(0, nbits);
 117         return bs;
 118     }
 119 
 120     /**
 121      * Load the primes up to the specified bound (inclusive) into a
 122      * {@code NavigableSet}, appending the prime {@code Integer.MAX_VALUE}.
 123      *
 124      * @param upperBound The maximum prime to allow
 125      * @return a set of primes
 126      */
 127     private static NavigableSet<BigInteger> getPrimes(int upperBound) {
 128         BitSet bs = createPrimes(upperBound);
 129         NavigableSet<BigInteger> primes = bs.stream()
 130                 .mapToObj(p -> BigInteger.valueOf(p + 2))
 131                 .collect(toCollection(TreeSet::new));
 132         primes.add(BigInteger.valueOf(Integer.MAX_VALUE));
 133         System.out.println(String.format("Created %d primes", primes.size()));
 134         return primes;
 135     }
 136 
 137     /**
 138      * Verifies whether the fraction of probable primes detected is at least 1 -
 139      * 1/2^certainty.
 140      *
 141      * @return true if and only if the test succeeds
 142      */
 143     private static boolean checkPrime(Set<BigInteger> primes,
 144             int certainty,
 145             boolean parallel) {
 146         long probablePrimes = (parallel ? primes.parallelStream() : primes.stream())
 147                 .filter(bi -> bi.isProbablePrime(certainty))
 148                 .count();
 149 
 150         // N = certainty / 2
 151         // Success if p/t >= 1 - 1/4^N
 152         // or (p/t)*4^N >= 4^N - 1
 153         // or p*4^N >= t*(4^N - 1)
 154         BigInteger p = BigInteger.valueOf(probablePrimes);
 155         BigInteger t = BigInteger.valueOf(primes.size());
 156         BigInteger fourToTheC = BigInteger.valueOf(4).pow(certainty / 2);
 157         BigInteger fourToTheCMinusOne = fourToTheC.subtract(BigInteger.ONE);
 158         BigInteger left = p.multiply(fourToTheC);
 159         BigInteger right = t.multiply(fourToTheCMinusOne);
 160 
 161         if (left.compareTo(right) < 0) {
 162             System.err.println("Probable prime certainty test failed");
 163         }
 164 
 165         return left.compareTo(right) >= 0;
 166     }
 167 
 168     /**
 169      * Verifies whether all {@code BigInteger}s in the tested range for which
 170      * {@code isProbablePrime()} returns {@code false} are <i>not</i>
 171      * prime numbers.
 172      *
 173      * @return true if and only if the test succeeds
 174      */
 175     private static boolean checkNonPrime(NavigableSet<BigInteger> primes,
 176             int certainty) {
 177         int maxPrime = DEFAULT_UPPER_BOUND;
 178         try {
 179             maxPrime = primes.last().intValueExact();
 180         } catch (ArithmeticException e) {
 181             // ignore it
 182         }
 183 
 184         // Create a list of non-prime BigIntegers.
 185         SplittableRandom splitRandom = RandomFactory.getSplittableRandom();
 186         List<BigInteger> nonPrimeBigInts = (splitRandom)
 187                 .ints(NUM_NON_PRIMES, 2, maxPrime).mapToObj(BigInteger::valueOf)
 188                 .filter(b -> !b.isProbablePrime(certainty)).collect(toList());
 189 
 190         // If there are any non-probable primes also in the primes list then fail.
 191         boolean failed = nonPrimeBigInts.stream().anyMatch(primes::contains);
 192 
 193         // In the event, print which purported non-primes were actually prime.
 194         if (failed) {
 195             for (BigInteger bigInt : nonPrimeBigInts) {
 196                 if (primes.contains(bigInt)) {
 197                     System.err.println("Prime value thought to be non-prime: " + bigInt);
 198                 }
 199             }
 200         }
 201 
 202         return !failed;
 203     }
 204 
 205     /**
 206      * Verifies whether a specified subset of Mersenne primes are correctly
 207      * identified as being prime. See
 208      * <a href="https://en.wikipedia.org/wiki/Mersenne_prime">Mersenne prime</a>
 209      * for more information.
 210      *
 211      * @return true if and only if the test succeeds
 212      */
 213     private static boolean checkMersennePrimes(int certainty) {
 214         int[] MERSENNE_EXPONENTS = {
 215             2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203,
 216             2281, 3217, 4253, // uncomment remaining array elements to make this test run a long time
 217             /* 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497,
 218             86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269,
 219             2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951,
 220             30402457, 32582657, 37156667, 42643801, 43112609, 57885161 */
 221         };
 222         System.out.println("Checking first "+MERSENNE_EXPONENTS.length+" Mersenne primes");
 223 
 224         boolean result = true;
 225         for (int n : MERSENNE_EXPONENTS) {
 226             BigInteger mp = BigInteger.ONE.shiftLeft(n).subtract(BigInteger.ONE);
 227             if (!mp.isProbablePrime(certainty)) {
 228                 System.err.println("Mp with p = "+n+" not classified as prime");
 229                 result = false;
 230             }
 231         }
 232 
 233         return result;
 234     }
 235 }