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.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  */
23 
24 /*
25  * @test
26  * @library /test/lib
27  * @build jdk.test.lib.RandomFactory
28  * @run main PrimeTest
29  * @bug 8026236 8074460 8078672
30  * @summary test primality verification methods in BigInteger (use -Dseed=X to set PRNG seed)
31  * @author bpb
32  * @key randomness
33  */
34 package test.java.math.BigInteger;
35 
36 import java.math.BigInteger;
37 import java.util.BitSet;
38 import java.util.List;
39 import java.util.NavigableSet;
40 import java.util.Set;
41 import java.util.SplittableRandom;
42 import java.util.TreeSet;
43 import static java.util.stream.Collectors.toCollection;
44 import static java.util.stream.Collectors.toList;
45 
46 import android.platform.test.annotations.LargeTest;
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     @LargeTest
59     @Test
testPrimes()60     public void testPrimes() throws Exception {
61         // Get primes through specified bound (inclusive) and Integer.MAX_VALUE
62         NavigableSet<BigInteger> primes = getPrimes();
63 
64         // Check whether known primes are identified as such
65         checkPrime(primes, DEFAULT_CERTAINTY);
66 
67         // Check whether known non-primes are not identified as primes
68         checkNonPrime(primes, DEFAULT_CERTAINTY);
69 
70         checkMersennePrimes(DEFAULT_CERTAINTY);
71     }
72 
73     /**
74      * Create a {@code BitSet} wherein a set bit indicates the corresponding
75      * index plus 2 is prime. That is, if bit N is set, then the integer N + 2
76      * is prime. The values 0 and 1 are intentionally excluded. See the
77      * <a
78      * href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_description">
79      * Sieve of Eratosthenes</a> algorithm description for more information.
80      *
81      * @return bits indicating which indexes represent primes
82      */
createPrimes()83     private static BitSet createPrimes() {
84         int nbits = PrimeTest.DEFAULT_UPPER_BOUND - 1;
85         BitSet bs = new BitSet(nbits);
86         for (int p = 2; p * p < PrimeTest.DEFAULT_UPPER_BOUND;) {
87             for (int i = p * p; i < nbits + 2; i += p) {
88                 bs.set(i - 2, true);
89             }
90             do {
91                 ++p;
92             } while (p > 1 && bs.get(p - 2));
93         }
94         bs.flip(0, nbits);
95         return bs;
96     }
97 
98     /**
99      * Load the primes up to the specified bound (inclusive) into a
100      * {@code NavigableSet}, appending the prime {@code Integer.MAX_VALUE}.
101      *
102      * @return a set of primes
103      */
getPrimes()104     private static NavigableSet<BigInteger> getPrimes() {
105         BitSet bs = createPrimes();
106         NavigableSet<BigInteger> primes = bs.stream()
107                 .mapToObj(p -> BigInteger.valueOf(p + 2))
108                 .collect(toCollection(TreeSet::new));
109         primes.add(BigInteger.valueOf(Integer.MAX_VALUE));
110         return primes;
111     }
112 
113     /**
114      * Verifies whether the fraction of probable primes detected is at least 1 -
115      * 1/2^certainty.
116      */
checkPrime(Set<BigInteger> primes, int certainty)117     private static void checkPrime(Set<BigInteger> primes, int certainty) {
118         long probablePrimes = (primes.parallelStream())
119                 .filter(bi -> bi.isProbablePrime(certainty))
120                 .count();
121 
122         // N = certainty / 2
123         // Success if p/t >= 1 - 1/4^N
124         // or (p/t)*4^N >= 4^N - 1
125         // or p*4^N >= t*(4^N - 1)
126         BigInteger p = BigInteger.valueOf(probablePrimes);
127         BigInteger t = BigInteger.valueOf(primes.size());
128         BigInteger fourToTheC = BigInteger.valueOf(4).pow(certainty / 2);
129         BigInteger fourToTheCMinusOne = fourToTheC.subtract(BigInteger.ONE);
130         BigInteger left = p.multiply(fourToTheC);
131         BigInteger right = t.multiply(fourToTheCMinusOne);
132 
133         Assert.assertFalse(left.compareTo(right) < 0,
134                 "Probable prime certainty test failed");
135     }
136 
137     /**
138      * Verifies whether all {@code BigInteger}s in the tested range for which
139      * {@code isProbablePrime()} returns {@code false} are <i>not</i>
140      * prime numbers.
141      */
142     private static void checkNonPrime(NavigableSet<BigInteger> primes, int certainty) {
143         int maxPrime = DEFAULT_UPPER_BOUND;
144         try {
145             maxPrime = primes.last().intValueExact();
146         } catch (ArithmeticException e) {
147             // ignore it
148         }
149 
150         // Create a list of non-prime BigIntegers.
151         SplittableRandom splitRandom = new SplittableRandom(0L);
152         List<BigInteger> nonPrimeBigInts = (splitRandom)
153                 .ints(NUM_NON_PRIMES, 2, maxPrime).mapToObj(BigInteger::valueOf)
154                 .filter(b -> !b.isProbablePrime(certainty)).collect(toList());
155 
156         // If there are any non-probable primes also in the primes list then fail.
157         boolean failed = nonPrimeBigInts.stream().anyMatch(primes::contains);
158 
159         // In the event, print which purported non-primes were actually prime.
160         if (failed) {
161             for (BigInteger bigInt : nonPrimeBigInts) {
162                 if (primes.contains(bigInt)) {
163                     Assert.fail("Prime value thought to be non-prime: " + bigInt);
164                 }
165             }
166         }
167     }
168 
169     /**
170      * Verifies whether a specified subset of Mersenne primes are correctly
171      * identified as being prime. See
172      * <a href="https://en.wikipedia.org/wiki/Mersenne_prime">Mersenne prime</a>
173      * for more information.
174      */
checkMersennePrimes(int certainty)175     private static void checkMersennePrimes(int certainty) {
176         int[] MERSENNE_EXPONENTS = {
177             2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203,
178             2281, 3217, 4253, // uncomment remaining array elements to make this test run a long time
179             /* 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497,
180             86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269,
181             2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951,
182             30402457, 32582657, 37156667, 42643801, 43112609, 57885161 */
183         };
184 
185         for (int n : MERSENNE_EXPONENTS) {
186             BigInteger mp = BigInteger.ONE.shiftLeft(n).subtract(BigInteger.ONE);
187             Assert.assertTrue(mp.isProbablePrime(certainty),
188                     "Mp with p = "+n+" not classified as prime");
189         }
190     }
191 }
192