1 /*
2 * Copyright (c) 2014, 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 * @bug 8026236
29 * @summary test primality verification methods in BigInteger
30 * @author bpb
31 */
32 import java.io.BufferedReader;
33 import java.io.File;
34 import java.io.FileInputStream;
35 import java.io.FileNotFoundException;
36 import java.io.IOException;
37 import java.io.InputStream;
38 import java.io.InputStreamReader;
39 import java.math.BigInteger;
40 import java.net.URL;
41 import java.util.NavigableSet;
42 import java.util.Random;
43 import java.util.TreeSet;
44 import static java.util.stream.Collectors.toCollection;
45 import java.util.stream.Stream;
46 import java.util.zip.GZIPInputStream;
47
48 public class PrimeTest {
49
50 private static final String DEFAULT_PRIMES_FILE = "primes-100000.txt.gz";
51 private static final int DEFAULT_MAX_NUM_PRIMES = 1000000;
52 private static final int DEFAULT_CERTAINTY = 100;
53 private static final int NUM_NON_PRIMES = 10000;
54 private static final String DEFAULT_PRIMES_SOURCE;
55
56 // Set up default prime number source
57 static {
58 try {
59 String dir = System.getProperty("test.src", ".");
60 File testFile = new File(dir, DEFAULT_PRIMES_FILE);
61 DEFAULT_PRIMES_SOURCE = testFile.getAbsolutePath();
62 } catch (Throwable t) {
63 throw new Error(t);
64 }
65 }
66
67 /**
68 * Run the test.
69 *
70 * @param args The parameters. The zeroth parameter should be either a file
71 * path or a URL string.
72 * @throws Throwable
73 */
74 public static void main(String[] args) throws Throwable {
75 // Prepare arguments
76 String primesSource = args.length > 0 ? args[0] : DEFAULT_PRIMES_SOURCE;
77 int maxNumPrimes = args.length > 1 ? Integer.valueOf(args[1]) : DEFAULT_MAX_NUM_PRIMES;
78 int certainty = args.length > 2 ? Integer.valueOf(args[2]) : DEFAULT_CERTAINTY;
79 boolean parallel = args.length > 3 ? Boolean.valueOf(args[3]) : true;
80
81 // Echo parameter settings
82 System.out.println("Primes source: " + primesSource + "\nupper bound = " + maxNumPrimes
83 + "\ncertainty = " + certainty
84 + "\nparallel = " + parallel);
85
86 // Check whether known primes are identified as such
87 boolean primeTest = checkPrime(primesSource, maxNumPrimes, certainty, parallel);
88 System.out.println("Prime test result: " + (primeTest ? "SUCCESS" : "FAILURE"));
89 if (!primeTest) {
90 System.err.println("Prime test failed");
91 }
92
93 // Check whether known non-primes are not identified as primes
94 boolean nonPrimeTest = checkNonPrime(primesSource, maxNumPrimes, certainty);
95 System.out.println("Non-prime test result: " + (nonPrimeTest ? "SUCCESS" : "FAILURE"));
96
97 if (!primeTest || !nonPrimeTest) {
98 throw new Exception("PrimeTest FAILED!");
99 }
100
101 System.out.println("PrimeTest succeeded!");
102 }
103
104 /**
105 * Parse the primes into a list of [@code BigInteger}s.
106 *
107 * @param gis InputStream of prime numbers assumed to be from a GZIPped text
108 * file with one number per line in the default character set
109 * @param n The maximum number of primes to load
110 * @return A {@code NavigableSet<BigInteger>} containing the loaded primes
111 * @throws IOException If something nasty happens
112 */
113 private static NavigableSet<BigInteger> parsePrimesStream(InputStream is, long n) throws IOException {
114 GZIPInputStream gis = new GZIPInputStream(is);
115 BufferedReader br = new BufferedReader(new InputStreamReader(gis));
116 try (Stream<String> lines = br.lines()) {
117 return lines.limit(n).map(BigInteger::new).collect(toCollection(TreeSet::new));
118 }
119 }
120
121 private static NavigableSet<BigInteger> parsePrimesFile(File f, long n) throws IOException {
122 InputStream gis = new FileInputStream(f);
123 return parsePrimesStream(gis, n);
124 }
125
126 private static NavigableSet<BigInteger> parsePrimesURL(URL u, long n) throws IOException {
127 InputStream is = u.openStream();
128 return parsePrimesStream(is, n);
129 }
130
131 private static NavigableSet<BigInteger> parsePrimes(String primesSource, long n) throws IOException {
132 File file = new File(primesSource);
133 if (file.exists()) {
134 return parsePrimesFile(file, n);
135 } else {
136 URL url = new URL(primesSource);
137 return parsePrimesURL(url, n);
138 }
139 }
140
141 /**
142 * Verifies whether the fraction of probable primes detected is at least 1 -
143 * 1/2^certainty.
144 *
145 * @return true if and only if the test succeeds
146 */
147 private static boolean checkPrime(String primesSource, int maxNumPrimes,
148 int certainty,
149 boolean parallel) throws FileNotFoundException, IOException {
150
151 NavigableSet<BigInteger> primes = parsePrimes(primesSource, maxNumPrimes);
152
153 System.out.println(String.format("Loaded %d primes", primes.size()));
154
155 long probablePrimes = (parallel ? primes.parallelStream() : primes.stream())
156 .filter(bi -> bi.isProbablePrime(certainty))
157 .count();
158
159 System.out.println(probablePrimes + " probable primes out of "
160 + primes.size() + " candidates");
161 if (probablePrimes != primes.size()) {
162 System.err.println("Number of probable primes unequal to number of actual primes");
163 }
164
165 // N = certainty / 2
166 // Success if p/t >= 1 - 1/4^N
167 // or (p/t)*4^N >= 4^N - 1
168 // or p*4^N >= t*(4^N - 1)
169 BigInteger p = BigInteger.valueOf(probablePrimes);
170 BigInteger t = BigInteger.valueOf(primes.size());
171 BigInteger fourToTheC = BigInteger.valueOf(4).pow(certainty / 2);
172 BigInteger fourToTheCMinusOne = fourToTheC.subtract(BigInteger.ONE);
173 BigInteger left = p.multiply(fourToTheC);
174 BigInteger right = t.multiply(fourToTheCMinusOne);
175
176 if (left.compareTo(right) < 0) {
177 System.err.println("Probable prime certainty test failed.");
178 }
179
180 return left.compareTo(right) >= 0;
181 }
182
183 /**
184 * Verifies whether all {@code BigInteger}s in the tested range for which
185 * {@code isProbablePrime()} returns {@code false} are <i>not</i>
186 * prime numbers.
187 *
188 * @return true if and only if the test succeeds
189 */
190 private static boolean checkNonPrime(String primesSource, int maxNumPrimes,
191 int certainty) throws FileNotFoundException, IOException {
192 NavigableSet<BigInteger> primes = parsePrimes(primesSource, maxNumPrimes);
193
194 int maxPrime = 100000;
195 try {
196 maxPrime = primes.last().intValueExact();
197 } catch (ArithmeticException e) {
198 // ignore it
199 }
200
201 // If it's not a probable prime but is in the primes list then fail.
202 boolean result = !(new Random()).ints(NUM_NON_PRIMES, 2, maxPrime).mapToObj(BigInteger::valueOf).filter(b -> !b.isProbablePrime(certainty)).anyMatch(primes::contains);
203
204 return result;
205 }
206 }