|
Java program Miller-Rabin primality test
|
| bet | 11/12 | | Sana | 05.12.2023 | | Hajmi | 385,21 Kb. | | #111359 |
Java program Miller-Rabin primality test
import java.io.*;
import java.math.*;
class GFG {
// Utility function to do modular // exponentiation. It returns (x^y) % p
static int power(int x, int y, int p) {
int res = 1; // Initialize result
//Update x if it is more than or
// equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x with result if ((y & 1) == 1)
res = (res * x) % p;
// y must be even now y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// This function is called for all k trials. // It returns false if n is composite and
// returns false if n is probably prime.
// d is an odd number such that d*2r
// = n-1 for some r >= 1 static boolean miillerTest(int d, int n) { // Pick a
random number in [2..n-2] // Corner cases make sure that n > 4
int a = 2 + (int)(Math.random() % (n - 4));
// Compute a^d % n
int x = power(a, d, n);
if (x == 1 || x == n - 1)
return true;
// Keep squaring x while one of the
// following doesn't happen
// (i) d does not reach n-1
// (ii) (x^2) % n is not 1 // (iii) (x^2) % n is not n-1 while (d != n - 1)
{ x = (x * x) % n;
d *= 2;
if (x == 1) return false; if (x == n - 1) return
true;
}
// Return composite return false;
}
// It returns false if n is composite
// and returns true if n is probably
// prime. k is an input parameter that // determines accuracy level. Higher //
value of k indicates more accuracy. static boolean isPrime(int n, int k) {
// Corner cases if (n <= 1 || n == 4) return false; if (n <= 3)
return true;
// Find r such that n = 2^d * r + 1
// for some r >= 1
int d = n - 1;
while (d % 2 == 0) d /= 2;
// Iterate given nber of 'k' times for (int i = 0; i < k; i++) if
(!miillerTest(d, n))
return false;
return true;
}
// Driver program
public static void main(String args[])
{
int k = 4; // Number of iterations
System.out.println("All primes smaller "
+ "than 100: ");
for (int n = 1; n < 100; n++) if (isPrime(n, k))
System.out.print(n >+ " ");
}
}
|
| |
