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:
Java Program to Implement Cubic convergence 1/pi Algorithm
Java Program to Implement Bucket Sort
Java Program to Compute the Volume of a Tetrahedron Using Determinants
Java Program to implement Bi Directional Map
Introduction to Eclipse Collections
Java Program to Perform Optimal Paranthesization Using Dynamic Programming
Optional trong Java 8
Java Program to find the number of occurrences of a given number using Binary Search approach
Spring Boot - Code Structure
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not
HandlerAdapters in Spring MVC
Phương thức tham chiếu trong Java 8 – Method References
Primitive Type Streams in Java 8
Split a String in Java
Database Migrations with Flyway
Java Program to Find Inverse of a Matrix
Java Program to Create a Random Graph Using Random Edge Generation
Generic Constructors in Java
Java 8 – Powerful Comparison with Lambdas
Implementing a Runnable vs Extending a Thread
Hướng dẫn sử dụng Java String, StringBuffer và StringBuilder
Java Program to Implement RoleList API
Java Program to Perform String Matching Using String Library
Java Program to Find a Good Feedback Vertex Set
The HttpMediaTypeNotAcceptableException in Spring MVC
Inheritance with Jackson
Batch Processing with Spring Cloud Data Flow
Java Program to Convert a Decimal Number to Binary Number using Stacks
Netflix Archaius with Various Database Configurations
Java Program to Describe the Representation of Graph using Incidence List
Spring Boot - Admin Server
Java Program to Implement the Hill Cypher