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 package test.java.math.BigInteger; 37 38 import java.math.BigInteger; 39 import java.util.BitSet; 40 import java.util.List; 41 import java.util.NavigableSet; 42 import java.util.Set; 43 import java.util.SplittableRandom; 44 import java.util.TreeSet; 45 import static java.util.stream.Collectors.toCollection; 46 import static java.util.stream.Collectors.toList; 47 48 import org.testng.Assert; 49 import org.testng.annotations.Test; 50 51 // Android-changed: Replace error printing with asserts. 52 public class PrimeTest { 53 54 private static final int DEFAULT_UPPER_BOUND = 1299709; // 100000th prime 55 private static final int DEFAULT_CERTAINTY = 100; 56 private static final int NUM_NON_PRIMES = 10000; 57 58 @Test testPrimes()59 public void testPrimes() throws Exception { 60 // Get primes through specified bound (inclusive) and Integer.MAX_VALUE 61 NavigableSet<BigInteger> primes = getPrimes(); 62 63 // Check whether known primes are identified as such 64 checkPrime(primes, DEFAULT_CERTAINTY); 65 66 // Check whether known non-primes are not identified as primes 67 checkNonPrime(primes, DEFAULT_CERTAINTY); 68 69 checkMersennePrimes(DEFAULT_CERTAINTY); 70 } 71 72 /** 73 * Create a {@code BitSet} wherein a set bit indicates the corresponding 74 * index plus 2 is prime. That is, if bit N is set, then the integer N + 2 75 * is prime. The values 0 and 1 are intentionally excluded. See the 76 * <a 77 * href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_description"> 78 * Sieve of Eratosthenes</a> algorithm description for more information. 79 * 80 * @return bits indicating which indexes represent primes 81 */ createPrimes()82 private static BitSet createPrimes() { 83 int nbits = PrimeTest.DEFAULT_UPPER_BOUND - 1; 84 BitSet bs = new BitSet(nbits); 85 for (int p = 2; p * p < PrimeTest.DEFAULT_UPPER_BOUND;) { 86 for (int i = p * p; i < nbits + 2; i += p) { 87 bs.set(i - 2, true); 88 } 89 do { 90 ++p; 91 } while (p > 1 && bs.get(p - 2)); 92 } 93 bs.flip(0, nbits); 94 return bs; 95 } 96 97 /** 98 * Load the primes up to the specified bound (inclusive) into a 99 * {@code NavigableSet}, appending the prime {@code Integer.MAX_VALUE}. 100 * 101 * @return a set of primes 102 */ getPrimes()103 private static NavigableSet<BigInteger> getPrimes() { 104 BitSet bs = createPrimes(); 105 NavigableSet<BigInteger> primes = bs.stream() 106 .mapToObj(p -> BigInteger.valueOf(p + 2)) 107 .collect(toCollection(TreeSet::new)); 108 primes.add(BigInteger.valueOf(Integer.MAX_VALUE)); 109 return primes; 110 } 111 112 /** 113 * Verifies whether the fraction of probable primes detected is at least 1 - 114 * 1/2^certainty. 115 */ checkPrime(Set<BigInteger> primes, int certainty)116 private static void checkPrime(Set<BigInteger> primes, int certainty) { 117 long probablePrimes = (primes.parallelStream()) 118 .filter(bi -> bi.isProbablePrime(certainty)) 119 .count(); 120 121 // N = certainty / 2 122 // Success if p/t >= 1 - 1/4^N 123 // or (p/t)*4^N >= 4^N - 1 124 // or p*4^N >= t*(4^N - 1) 125 BigInteger p = BigInteger.valueOf(probablePrimes); 126 BigInteger t = BigInteger.valueOf(primes.size()); 127 BigInteger fourToTheC = BigInteger.valueOf(4).pow(certainty / 2); 128 BigInteger fourToTheCMinusOne = fourToTheC.subtract(BigInteger.ONE); 129 BigInteger left = p.multiply(fourToTheC); 130 BigInteger right = t.multiply(fourToTheCMinusOne); 131 132 Assert.assertFalse(left.compareTo(right) < 0, 133 "Probable prime certainty test failed"); 134 } 135 136 /** 137 * Verifies whether all {@code BigInteger}s in the tested range for which 138 * {@code isProbablePrime()} returns {@code false} are <i>not</i> 139 * prime numbers. 140 */ 141 private static void checkNonPrime(NavigableSet<BigInteger> primes, int certainty) { 142 int maxPrime = DEFAULT_UPPER_BOUND; 143 try { 144 maxPrime = primes.last().intValueExact(); 145 } catch (ArithmeticException e) { 146 // ignore it 147 } 148 149 // Create a list of non-prime BigIntegers. 150 SplittableRandom splitRandom = new SplittableRandom(0L); 151 List<BigInteger> nonPrimeBigInts = (splitRandom) 152 .ints(NUM_NON_PRIMES, 2, maxPrime).mapToObj(BigInteger::valueOf) 153 .filter(b -> !b.isProbablePrime(certainty)).collect(toList()); 154 155 // If there are any non-probable primes also in the primes list then fail. 156 boolean failed = nonPrimeBigInts.stream().anyMatch(primes::contains); 157 158 // In the event, print which purported non-primes were actually prime. 159 if (failed) { 160 for (BigInteger bigInt : nonPrimeBigInts) { 161 if (primes.contains(bigInt)) { 162 Assert.fail("Prime value thought to be non-prime: " + bigInt); 163 } 164 } 165 } 166 } 167 168 /** 169 * Verifies whether a specified subset of Mersenne primes are correctly 170 * identified as being prime. See 171 * <a href="https://en.wikipedia.org/wiki/Mersenne_prime">Mersenne prime</a> 172 * for more information. 173 */ checkMersennePrimes(int certainty)174 private static void checkMersennePrimes(int certainty) { 175 int[] MERSENNE_EXPONENTS = { 176 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 177 2281, 3217, 4253, // uncomment remaining array elements to make this test run a long time 178 /* 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 179 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 180 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 181 30402457, 32582657, 37156667, 42643801, 43112609, 57885161 */ 182 }; 183 184 for (int n : MERSENNE_EXPONENTS) { 185 BigInteger mp = BigInteger.ONE.shiftLeft(n).subtract(BigInteger.ONE); 186 Assert.assertTrue(mp.isProbablePrime(certainty), 187 "Mp with p = "+n+" not classified as prime"); 188 } 189 } 190 } 191