1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17
18// BEGIN android-note
19// Since the original Harmony Code of the BigInteger class was strongly modified,
20// in order to use the more efficient OpenSSL BIGNUM implementation,
21// no android-modification-tags were placed, at all.
22// END android-note
23
24package java.math;
25
26import java.util.Arrays;
27
28/**
29 * Provides primality probabilistic methods.
30 */
31class Primality {
32
33    /** Just to denote that this class can't be instantiated. */
34    private Primality() {}
35
36    /** All prime numbers with bit length lesser than 10 bits. */
37    private static final int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
38            31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
39            103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
40            173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
41            241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
42            317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
43            401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
44            479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
45            571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
46            647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
47            739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
48            827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
49            919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009,
50            1013, 1019, 1021 };
51
52    /** All {@code BigInteger} prime numbers with bit length lesser than 10 bits. */
53    private static final BigInteger BIprimes[] = new BigInteger[primes.length];
54
55//    /**
56//     * It encodes how many iterations of Miller-Rabin test are need to get an
57//     * error bound not greater than {@code 2<sup>(-100)</sup>}. For example:
58//     * for a {@code 1000}-bit number we need {@code 4} iterations, since
59//     * {@code BITS[3] < 1000 <= BITS[4]}.
60//     */
61//    private static final int[] BITS = { 0, 0, 1854, 1233, 927, 747, 627, 543,
62//            480, 431, 393, 361, 335, 314, 295, 279, 265, 253, 242, 232, 223,
63//            216, 181, 169, 158, 150, 145, 140, 136, 132, 127, 123, 119, 114,
64//            110, 105, 101, 96, 92, 87, 83, 78, 73, 69, 64, 59, 54, 49, 44, 38,
65//            32, 26, 1 };
66//
67//    /**
68//     * It encodes how many i-bit primes there are in the table for
69//     * {@code i=2,...,10}. For example {@code offsetPrimes[6]} says that from
70//     * index {@code 11} exists {@code 7} consecutive {@code 6}-bit prime
71//     * numbers in the array.
72//     */
73//    private static final int[][] offsetPrimes = { null, null, { 0, 2 },
74//            { 2, 2 }, { 4, 2 }, { 6, 5 }, { 11, 7 }, { 18, 13 }, { 31, 23 },
75//            { 54, 43 }, { 97, 75 } };
76
77    static {// To initialize the dual table of BigInteger primes
78        for (int i = 0; i < primes.length; i++) {
79            BIprimes[i] = BigInteger.valueOf(primes[i]);
80        }
81    }
82
83    /**
84     * It uses the sieve of Eratosthenes to discard several composite numbers in
85     * some appropriate range (at the moment {@code [this, this + 1024]}). After
86     * this process it applies the Miller-Rabin test to the numbers that were
87     * not discarded in the sieve.
88     *
89     * @see BigInteger#nextProbablePrime()
90     */
91    static BigInteger nextProbablePrime(BigInteger n) {
92        // PRE: n >= 0
93        int i, j;
94//        int certainty;
95        int gapSize = 1024; // for searching of the next probable prime number
96        int[] modules = new int[primes.length];
97        boolean isDivisible[] = new boolean[gapSize];
98        BigInt ni = n.getBigInt();
99        // If n < "last prime of table" searches next prime in the table
100        if (ni.bitLength() <= 10) {
101            int l = (int)ni.longInt();
102            if (l < primes[primes.length - 1]) {
103                for (i = 0; l >= primes[i]; i++) {}
104                return BIprimes[i];
105            }
106        }
107
108        BigInt startPoint = ni.copy();
109        BigInt probPrime = new BigInt();
110
111        // Fix startPoint to "next odd number":
112        startPoint.addPositiveInt(BigInt.remainderByPositiveInt(ni, 2) + 1);
113
114//        // To set the improved certainty of Miller-Rabin
115//        j = startPoint.bitLength();
116//        for (certainty = 2; j < BITS[certainty]; certainty++) {
117//            ;
118//        }
119
120        // To calculate modules: N mod p1, N mod p2, ... for first primes.
121        for (i = 0; i < primes.length; i++) {
122            modules[i] = BigInt.remainderByPositiveInt(startPoint, primes[i]) - gapSize;
123        }
124        while (true) {
125            // At this point, all numbers in the gap are initialized as
126            // probably primes
127            Arrays.fill(isDivisible, false);
128            // To discard multiples of first primes
129            for (i = 0; i < primes.length; i++) {
130                modules[i] = (modules[i] + gapSize) % primes[i];
131                j = (modules[i] == 0) ? 0 : (primes[i] - modules[i]);
132                for (; j < gapSize; j += primes[i]) {
133                    isDivisible[j] = true;
134                }
135            }
136            // To execute Miller-Rabin for non-divisible numbers by all first
137            // primes
138            for (j = 0; j < gapSize; j++) {
139                if (!isDivisible[j]) {
140                    probPrime.putCopy(startPoint);
141                    probPrime.addPositiveInt(j);
142                    if (probPrime.isPrime(100)) {
143                        return new BigInteger(probPrime);
144                    }
145                }
146            }
147            startPoint.addPositiveInt(gapSize);
148        }
149    }
150
151}
152