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