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.math.BigInteger;

    33 import java.util.BitSet;

    34 import java.util.List;

    35 import java.util.NavigableSet;

    36 import java.util.SplittableRandom;

    37 import java.util.TreeSet;

    38 import static java.util.stream.Collectors.toCollection;

    39 import static java.util.stream.Collectors.toList;

    40 import java.util.stream.IntStream;

    41 import java.util.stream.Stream;

    42 

    43 public class PrimeTest {

    44 

    45     private static final int DEFAULT_UPPER_BOUND = 1299709; // 100000th prime

    46     private static final int DEFAULT_CERTAINTY = 100;

    47     private static final int NUM_NON_PRIMES = 10000;

    48 

    49     /**

    50      * Run the test.

    51      *

    52      * @param args The parameters.

    53      * @throws Exception on failure

    54      */

    55     public static void main(String[] args) throws Exception {

    56         // Prepare arguments

    57         int upperBound = args.length > 0 ? Integer.valueOf(args[0]) : DEFAULT_UPPER_BOUND;

    58         int certainty = args.length > 1 ? Integer.valueOf(args[1]) : DEFAULT_CERTAINTY;

    59         boolean parallel = args.length > 2 ? Boolean.valueOf(args[2]) : true;

    60 

    61         // Echo parameter settings

    62         System.out.println("Upper bound = " + upperBound

    63                 + "\nCertainty = " + certainty

    64                 + "\nParallel = " + parallel);

    65 

    66         // Get primes through specified bound (inclusive) and Integer.MAX_VALUE

    67         NavigableSet<BigInteger> primes = getPrimes(upperBound);

    68 

    69         // Check whether known primes are identified as such

    70         boolean primeTest = checkPrime(primes, certainty, parallel);

    71         System.out.println("Prime test result: " + (primeTest ? "SUCCESS" : "FAILURE"));

    72         if (!primeTest) {

    73             System.err.println("Prime test failed");

    74         }

    75 

    76         // Check whether known non-primes are not identified as primes

    77         boolean nonPrimeTest = checkNonPrime(primes, certainty);

    78         System.out.println("Non-prime test result: " + (nonPrimeTest ? "SUCCESS" : "FAILURE"));

    79 

    80         if (!primeTest || !nonPrimeTest) {

    81             throw new Exception("PrimeTest FAILED!");

    82         }

    83 

    84         System.out.println("PrimeTest succeeded!");

    85     }

    86 

    87     /**

    88      * Create a {@code BitSet} wherein a set bit indicates the corresponding

    89      * index plus 2 is prime. That is, if bit N is set, then the integer N + 2

    90      * is prime. The values 0 and 1 are intentionally excluded. See the

    91      * <a

    92      * href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_description">

    93      * Sieve of Eratosthenes</a> algorithm description for more information.

    94      *

    95      * @param upperBound The maximum prime to allow

    96      * @return bits indicating which indexes represent primes

    97      */

    98     private static BitSet createPrimes(int upperBound) {

    99         int nbits = upperBound - 1;

   100         BitSet bs = new BitSet(nbits);

   101         for (int p = 2; p * p < upperBound;) {

   102             for (int i = p * p; i < nbits + 2; i += p) {

   103                 bs.set(i - 2, true);

   104             }

   105             do {

   106                 ++p;

   107             } while (p > 1 && bs.get(p - 2));

   108         }

   109         bs.flip(0, nbits);

   110         return bs;

   111     }

   112 

   113     /**

   114      * Load the primes up to the specified bound (inclusive) into a

   115      * {@code NavigableSet}, appending the prime {@code Integer.MAX_VALUE}.

   116      *

   117      * @param upperBound The maximum prime to allow

   118      * @return a set of primes

   119      */

   120     private static NavigableSet<BigInteger> getPrimes(int upperBound) {

   121         BitSet bs = createPrimes(upperBound);

   122         NavigableSet<BigInteger> primes = bs.stream()

   123                 .mapToObj(p -> BigInteger.valueOf(p + 2))

   124                 .collect(toCollection(TreeSet::new));

   125         primes.add(BigInteger.valueOf(Integer.MAX_VALUE));

   126         System.out.println(String.format("Created %d primes", primes.size()));

   127         return primes;

   128     }

   129 

   130     /**

   131      * Verifies whether the fraction of probable primes detected is at least 1 -

   132      * 1/2^certainty.

   133      *

   134      * @return true if and only if the test succeeds

   135      */

   136     private static boolean checkPrime(NavigableSet<BigInteger> primes,

   137             int certainty,

   138             boolean parallel) {

   139         long probablePrimes = (parallel ? primes.parallelStream() : primes.stream())

   140                 .filter(bi -> bi.isProbablePrime(certainty))

   141                 .count();

   142 

   143         // N = certainty / 2

   144         // Success if p/t >= 1 - 1/4^N

   145         // or (p/t)*4^N >= 4^N - 1

   146         // or p*4^N >= t*(4^N - 1)

   147         BigInteger p = BigInteger.valueOf(probablePrimes);

   148         BigInteger t = BigInteger.valueOf(primes.size());

   149         BigInteger fourToTheC = BigInteger.valueOf(4).pow(certainty / 2);

   150         BigInteger fourToTheCMinusOne = fourToTheC.subtract(BigInteger.ONE);

   151         BigInteger left = p.multiply(fourToTheC);

   152         BigInteger right = t.multiply(fourToTheCMinusOne);

   153 

   154         if (left.compareTo(right) < 0) {

   155             System.err.println("Probable prime certainty test failed.");

   156         }

   157 

   158         return left.compareTo(right) >= 0;

   159     }

   160 

   161     /**

   162      * Verifies whether all {@code BigInteger}s in the tested range for which

   163      * {@code isProbablePrime()} returns {@code false} are <i>not</i>

   164      * prime numbers.

   165      *

   166      * @return true if and only if the test succeeds

   167      */

   168     private static boolean checkNonPrime(NavigableSet<BigInteger> primes,

   169             int certainty) {

   170         int maxPrime = DEFAULT_UPPER_BOUND;

   171         try {

   172             maxPrime = primes.last().intValueExact();

   173         } catch (ArithmeticException e) {

   174             // ignore it

   175         }

   176 

   177         // Create a list of non-prime BigIntegers.

   178         List<BigInteger> nonPrimeBigInts = (new SplittableRandom())

   179                 .ints(NUM_NON_PRIMES, 2, maxPrime).mapToObj(BigInteger::valueOf)

   180                 .filter(b -> !b.isProbablePrime(certainty)).collect(toList());

   181 

   182         // If there are any non-probable primes also in the primes list then fail.

   183         boolean failed = nonPrimeBigInts.stream().anyMatch(primes::contains);

   184 

   185         // In the event, print which purported non-primes were actually prime.

   186         if (failed) {

   187             for (BigInteger bigInt : nonPrimeBigInts) {

   188                 if (primes.contains(bigInt)) {

   189                     System.err.println("Prime value thought to be non-prime: " + bigInt);

   190                 }

   191             }

   192         }

   193 

   194         return !failed;

   195     }

   196 }