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