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
33 import java.io.BufferedReader;
34 import java.io.File;
35 import java.io.FileInputStream;
36 import java.io.FileNotFoundException;
37 import java.io.IOException;
38 import java.io.InputStreamReader;
39 import java.math.BigInteger;
40 import java.util.List;
41 import java.util.Random;
42 import static java.util.stream.Collectors.toList;
43 import java.util.stream.Stream;
44 import java.util.zip.GZIPInputStream;
45
46 public class PrimeTest {
47 private static final String DEFAULT_PRIMES_FILE;
48 private static final int DEFAULT_UPPER_BOUND = 1000000;
49 private static final int DEFAULT_CERTAINTY = 100;
50
51 static {
52 try {
53 String dir = System.getProperty("test.src", ".");
54 File testFile = new File(dir, "primes-100000.txt.gz");
55 DEFAULT_PRIMES_FILE = testFile.getAbsolutePath();
56 } catch (Throwable t) {
57 throw new Error(t);
58 }
59 }
60
61 public static void main(String[] args) throws Throwable {
62 // Prepare arguments
63 File primesFile = args.length > 0 ? new File(args[0]) : new File(DEFAULT_PRIMES_FILE);
64 int upperBound = args.length > 1 ? Integer.valueOf(args[1]) : DEFAULT_UPPER_BOUND;
65 int certainty = args.length > 2 ? Integer.valueOf(args[2]) : DEFAULT_CERTAINTY;
66 boolean parallel = args.length > 3 ? Boolean.valueOf(args[3]) : true;
67
68 // Echo parameter settings
69 System.out.println("Primes: " + primesFile + "\nupper bound = " + upperBound
70 + "\ncertainty = " + certainty
71 + "\nparallel = " + parallel);
72
73 boolean primeTest = checkPrime(primesFile, upperBound, 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 boolean notPrimeTest = checkNotPrime(primesFile, upperBound, certainty);
80 System.out.println("Not-prime test result: " + (notPrimeTest ? "SUCCESS" : "FAILURE"));
81
82 if (!primeTest || !notPrimeTest) {
83 throw new Exception("PrimeTest FAILED!");
84 }
85 System.out.println("PrimeTest succeeded!");
86 }
87
88 /**
89 * Parse the primes into a list of [@code BigInteger}s.
90 *
91 * @param f File of prime numbers assumed to be a GZIPped text file with one
92 * number per line in the default character set
93 * @param n The maximum number of primes to load
94 * @return A {@code List<BigInteger>} containing the loaded primes
95 * @throws IOException If something nasty happens
96 */
97 private static List<BigInteger> parsePrimes(File f, long n) throws IOException {
98 GZIPInputStream gis = new GZIPInputStream(new FileInputStream(f));
99 BufferedReader br = new BufferedReader(new InputStreamReader(gis));
100 try (Stream<String> lines = br.lines()) {
101 return lines.limit(n).map(BigInteger::new).collect(toList());
102 }
103 }
104
105 /**
106 * Verifies whether the fraction of probable primes detected in the range
107 * [2,upperBound) is at least 1 - 1/2^certainty.
108 *
109 * @return true if and only if the test succeeds
110 */
111 private static boolean checkPrime(File primesFile, int upperBound,
112 int certainty,
113 boolean parallel) throws FileNotFoundException, IOException {
114
115 List<BigInteger> primes = parsePrimes(primesFile, upperBound);
116
117 System.out.println(String.format("Loaded %d primes", primes.size()));
118
119 long probablePrimes = (parallel ? primes.parallelStream() : primes.stream())
120 .filter(bi -> bi.isProbablePrime(certainty))
121 .count();
122
123 System.out.println(probablePrimes + " probable primes out of " +
124 primes.size() + " candidates");
125 if (probablePrimes != primes.size()) {
126 System.err.println("Number of probable primes unequal to number of actual primes");
127 }
128
129 // N = certainty / 2
130 // Success if p/t >= 1 - 1/4^N
131 // or (p/t)*4^N >= 4^N - 1
132 // or p*4^N >= t*(4^N - 1)
133 BigInteger p = BigInteger.valueOf(probablePrimes);
134 BigInteger t = BigInteger.valueOf(primes.size());
135 BigInteger fourToTheC = BigInteger.valueOf(4).pow(certainty / 2);
136 BigInteger fourToTheCMinusOne = fourToTheC.subtract(BigInteger.ONE);
137 BigInteger left = p.multiply(fourToTheC);
138 BigInteger right = t.multiply(fourToTheCMinusOne);
139
140 if (left.compareTo(right) < 0) {
141 System.err.println("Probable prime certainty test failed.");
142 }
143
144 return left.compareTo(right) >= 0;
145 }
146
147 /**
148 * Verifies whether all {@code BigInteger}s in the range [2,upperBound) for
149 * which {@code isProbablePrime()} returns {@code false} are <i>not</i>
150 * prime numbers.
151 *
152 * @return true if and only if the test succeeds
153 */
154 private static boolean checkNotPrime(File primesFile, int upperBound,
155 int certainty) throws FileNotFoundException, IOException {
156 List<BigInteger> primes = parsePrimes(primesFile, upperBound);
157
158 // If it's not a probable prime but is in the primes list then fail.
159 boolean result = !(new Random()).ints(2500, 0, 100000).mapToObj(i -> {return BigInteger.valueOf(i);}).filter(b -> !b.isProbablePrime(certainty)).anyMatch(c -> primes.contains(c));
160
161 return result;
162 }
163 }
164