|
| 1 | +package com.thealgorithms.maths; |
| 2 | + |
| 3 | +import java.util.Random; |
| 4 | + |
| 5 | +public class MillerRabinPrimalityCheck { |
| 6 | + |
| 7 | + /** |
| 8 | + * Check whether the given number is prime or not |
| 9 | + * MillerRabin algorithm is probabilistic. There is also an altered version which is deterministic. |
| 10 | + * https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test |
| 11 | + * https://cp-algorithms.com/algebra/primality_tests.html |
| 12 | + * |
| 13 | + * @param n Whole number which is tested on primality |
| 14 | + * @param k Number of iterations |
| 15 | + * If n is composite then running k iterations of the Miller–Rabin |
| 16 | + * test will declare n probably prime with a probability at most 4^(−k) |
| 17 | + * @return true or false whether the given number is probably prime or not |
| 18 | + */ |
| 19 | + |
| 20 | + public static boolean millerRabin(long n, int k) { // returns true if n is probably prime, else returns false. |
| 21 | + if (n < 4) return n == 2 || n == 3; |
| 22 | + |
| 23 | + int s = 0; |
| 24 | + long d = n - 1; |
| 25 | + while ((d & 1) == 0) { |
| 26 | + d >>= 1; |
| 27 | + s++; |
| 28 | + } |
| 29 | + Random rnd = new Random(); |
| 30 | + for (int i = 0; i < k; i++) { |
| 31 | + long a = 2 + rnd.nextLong(n) % (n - 3); |
| 32 | + if (checkComposite(n, a, d, s)) return false; |
| 33 | + } |
| 34 | + return true; |
| 35 | + } |
| 36 | + |
| 37 | + public static boolean deterministicMillerRabin(long n) { // returns true if n is prime, else returns false. |
| 38 | + if (n < 2) return false; |
| 39 | + |
| 40 | + int r = 0; |
| 41 | + long d = n - 1; |
| 42 | + while ((d & 1) == 0) { |
| 43 | + d >>= 1; |
| 44 | + r++; |
| 45 | + } |
| 46 | + |
| 47 | + for (int a : new int[] {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) { |
| 48 | + if (n == a) return true; |
| 49 | + if (checkComposite(n, a, d, r)) return false; |
| 50 | + } |
| 51 | + return true; |
| 52 | + } |
| 53 | + |
| 54 | + /** |
| 55 | + * Check if number n is composite (probabilistic) |
| 56 | + * |
| 57 | + * @param n Whole number which is tested for compositeness |
| 58 | + * @param a Random number (prime base) to check if it holds certain equality |
| 59 | + * @param d Number which holds this equation: 'n - 1 = 2^s * d' |
| 60 | + * @param s Number of twos in (n - 1) factorization |
| 61 | + * |
| 62 | + * @return true or false whether the numbers hold the equation or not |
| 63 | + * the equations are described on the websites mentioned at the beginning of the class |
| 64 | + */ |
| 65 | + private static boolean checkComposite(long n, long a, long d, int s) { |
| 66 | + long x = powerModP(a, d, n); |
| 67 | + if (x == 1 || x == n - 1) return false; |
| 68 | + for (int r = 1; r < s; r++) { |
| 69 | + x = powerModP(x, 2, n); |
| 70 | + if (x == n - 1) return false; |
| 71 | + } |
| 72 | + return true; |
| 73 | + } |
| 74 | + |
| 75 | + private static long powerModP(long x, long y, long p) { |
| 76 | + long res = 1; // Initialize result |
| 77 | + |
| 78 | + x = x % p; // Update x if it is more than or equal to p |
| 79 | + |
| 80 | + if (x == 0) return 0; // In case x is divisible by p; |
| 81 | + |
| 82 | + while (y > 0) { |
| 83 | + // If y is odd, multiply x with result |
| 84 | + if ((y & 1) == 1) res = multiplyModP(res, x, p); |
| 85 | + |
| 86 | + // y must be even now |
| 87 | + y = y >> 1; // y = y/2 |
| 88 | + x = multiplyModP(x, x, p); |
| 89 | + } |
| 90 | + return res; |
| 91 | + } |
| 92 | + |
| 93 | + private static long multiplyModP(long a, long b, long p) { |
| 94 | + long aHi = a >> 24; |
| 95 | + long aLo = a & ((1 << 24) - 1); |
| 96 | + long bHi = b >> 24; |
| 97 | + long bLo = b & ((1 << 24) - 1); |
| 98 | + long result = ((((aHi * bHi << 16) % p) << 16) % p) << 16; |
| 99 | + result += ((aLo * bHi + aHi * bLo) << 24) + aLo * bLo; |
| 100 | + return result % p; |
| 101 | + } |
| 102 | +} |
0 commit comments