This is a Java Program to Implement Miller Rabin Primality Test Algorithm. Miller Rabin Primality Test is an algorithm which is used to determine if a given number is prime or not.
Here is the source code of the Java Program to Implement Miller Rabin Primality Test Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/**
** Java Program to Implement Miller Rabin Primality Test Algorithm
**/
import java.util.Scanner;
import java.util.Random;
import java.math.BigInteger;
/** Class MillerRabin **/
public class MillerRabin
{
/** Function to check if prime or not **/
public boolean isPrime(long n, int iteration)
{
/** base case **/
if (n == 0 || n == 1)
return false;
/** base case - 2 is prime **/
if (n == 2)
return true;
/** an even number other than 2 is composite **/
if (n % 2 == 0)
return false;
long s = n - 1;
while (s % 2 == 0)
s /= 2;
Random rand = new Random();
for (int i = 0; i < iteration; i++)
{
long r = Math.abs(rand.nextLong());
long a = r % (n - 1) + 1, temp = s;
long mod = modPow(a, temp, n);
while (temp != n - 1 && mod != 1 && mod != n - 1)
{
mod = mulMod(mod, mod, n);
temp *= 2;
}
if (mod != n - 1 && temp % 2 == 0)
return false;
}
return true;
}
/** Function to calculate (a ^ b) % c **/
public long modPow(long a, long b, long c)
{
long res = 1;
for (int i = 0; i < b; i++)
{
res *= a;
res %= c;
}
return res % c;
}
/** Function to calculate (a * b) % c **/
public long mulMod(long a, long b, long mod)
{
return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(mod)).longValue();
}
/** Main function **/
public static void main (String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Miller Rabin Primality Algorithm Test\n");
/** Make an object of MillerRabin class **/
MillerRabin mr = new MillerRabin();
/** Accept number **/
System.out.println("Enter number\n");
long num = scan.nextLong();
/** Accept number of iterations **/
System.out.println("\nEnter number of iterations");
int k = scan.nextInt();
/** check if prime **/
boolean prime = mr.isPrime(num, k);
if (prime)
System.out.println("\n"+ num +" is prime");
else
System.out.println("\n"+ num +" is composite");
}
}
Output:
Miller Rabin Primality Algorithm Test Enter number 5510389 Enter number of iterations 2 5510389 is prime
Related posts:
Tạo ứng dụng Java RESTful Client với thư viện Retrofit
Java Program to do a Breadth First Search/Traversal on a graph non-recursively
Marker Interface trong Java
The XOR Operator in Java
Spring Boot - Twilio
Multi Dimensional ArrayList in Java
A Guide to Concurrent Queues in Java
Spring Security and OpenID Connect
Java Program to Implement Sorted Array
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Java Program to Construct an Expression Tree for an Prefix Expression
Java Program to Implement Dijkstra’s Algorithm using Set
Java Program to Implement Sorted Circularly Singly Linked List
Bootstrap a Web Application with Spring 5
Java Program to Implement Pagoda
Guide to Guava Table
Fixing 401s with CORS Preflights and Spring Security
Create a Custom Auto-Configuration with Spring Boot
Spring Boot - Thymeleaf
Java Program to Check whether Directed Graph is Connected using BFS
Java Program to Generate All Possible Combinations of a Given List of Numbers
Java Program to Implement vector
Java Program to Solve a Matching Problem for a Given Specific Case
Spring Boot - Scheduling
Introduction to Spring Data MongoDB
Chuyển đổi giữa các kiểu dữ liệu trong Java
Tính đóng gói (Encapsulation) trong java
Java Program to Implement Max Heap
Java Program to Implement Shoelace Algorithm
Split a String in Java
Number Formatting in Java
Vòng lặp for, while, do-while trong Java