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