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