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