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 Find ith Largest Number from a Given List Using Order-Statistic Algorithm
Java Program to Implement the Binary Counting Method to Generate Subsets of a Set
Java Program to find the peak element of an array using Binary Search approach
Spring Boot - Actuator
Java Program to Create the Prufer Code for a Tree
Custom JUnit 4 Test Runners
Iterating over Enum Values in Java
Java Program to Perform LU Decomposition of any Matrix
Comparing Long Values in Java
Java Program to Implement Depth-limited Search
Java Program to Check Cycle in a Graph using Topological Sort
Java Program to Represent Graph Using Incidence List
Introduction to Spring Data JDBC
Guide to Guava Table
Quick Guide to the Java StringTokenizer
Remove All Occurrences of a Specific Value from a List
Java Program to Find the Longest Path in a DAG
Refactoring Design Pattern với tính năng mới trong Java 8
ClassNotFoundException vs NoClassDefFoundError
Add Multiple Items to an Java ArrayList
Introduction to Project Reactor Bus
Java – Get Random Item/Element From a List
Java Program to do a Breadth First Search/Traversal on a graph non-recursively
Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range
Introduction to Liquibase Rollback
Spring Security Basic Authentication
Show Hibernate/JPA SQL Statements from Spring Boot
Prim's Algorithm
Comparing getPath(), getAbsolutePath(), and getCanonicalPath() in Java
Java Program to Implement the RSA Algorithm
Java Program to Implement D-ary-Heap
Java Program to Implement Graph Structured Stack