| static java.math.BigInteger | nextProbablePrime(java.math.BigInteger n)It uses the sieve of Eratosthenes to discard several composite numbers in
some appropriate range (at the moment {@code [this, this + 1024]}). After
this process it applies the Miller-Rabin test to the numbers that were
not discarded in the sieve.
// /**
// * It encodes how many iterations of Miller-Rabin test are need to get an
// * error bound not greater than {@code 2<sup>(-100)</sup>}. For example:
// * for a {@code 1000}-bit number we need {@code 4} iterations, since
// * {@code BITS[3] < 1000 <= BITS[4]}.
// */
// private static final int[] BITS = { 0, 0, 1854, 1233, 927, 747, 627, 543,
// 480, 431, 393, 361, 335, 314, 295, 279, 265, 253, 242, 232, 223,
// 216, 181, 169, 158, 150, 145, 140, 136, 132, 127, 123, 119, 114,
// 110, 105, 101, 96, 92, 87, 83, 78, 73, 69, 64, 59, 54, 49, 44, 38,
// 32, 26, 1 };
//
// /**
// * It encodes how many i-bit primes there are in the table for
// * {@code i=2,...,10}. For example {@code offsetPrimes[6]} says that from
// * index {@code 11} exists {@code 7} consecutive {@code 6}-bit prime
// * numbers in the array.
// */
// private static final int[][] offsetPrimes = { null, null, { 0, 2 },
// { 2, 2 }, { 4, 2 }, { 6, 5 }, { 11, 7 }, { 18, 13 }, { 31, 23 },
// { 54, 43 }, { 97, 75 } };
// To initialize the dual table of BigInteger primes
for (int i = 0; i < primes.length; i++) {
BIprimes[i] = BigInteger.valueOf(primes[i]);
}
// PRE: n >= 0
int i, j;
// int certainty;
int gapSize = 1024; // for searching of the next probable prime number
int modules[] = new int[primes.length];
boolean isDivisible[] = new boolean[gapSize];
BigInt ni = n.bigInt;
// If n < "last prime of table" searches next prime in the table
if (ni.bitLength() <= 10) {
int l = (int)ni.longInt();
if (l < primes[primes.length - 1]) {
for (i = 0; l >= primes[i]; i++) {}
return BIprimes[i];
}
}
BigInt startPoint = ni.copy();
BigInt probPrime = new BigInt();
// Fix startPoint to "next odd number":
startPoint.addPositiveInt(BigInt.remainderByPositiveInt(ni, 2) + 1);
// // To set the improved certainty of Miller-Rabin
// j = startPoint.bitLength();
// for (certainty = 2; j < BITS[certainty]; certainty++) {
// ;
// }
// To calculate modules: N mod p1, N mod p2, ... for first primes.
for (i = 0; i < primes.length; i++) {
modules[i] = BigInt.remainderByPositiveInt(startPoint, primes[i]) - gapSize;
}
while (true) {
// At this point, all numbers in the gap are initialized as
// probably primes
Arrays.fill(isDivisible, false);
// To discard multiples of first primes
for (i = 0; i < primes.length; i++) {
modules[i] = (modules[i] + gapSize) % primes[i];
j = (modules[i] == 0) ? 0 : (primes[i] - modules[i]);
for (; j < gapSize; j += primes[i]) {
isDivisible[j] = true;
}
}
// To execute Miller-Rabin for non-divisible numbers by all first
// primes
for (j = 0; j < gapSize; j++) {
if (!isDivisible[j]) {
probPrime.putCopy(startPoint);
probPrime.addPositiveInt(j);
if (probPrime.isPrime(100, null, null)) {
return new BigInteger(probPrime);
}
}
}
startPoint.addPositiveInt(gapSize);
}
|
