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:
Check if there is mail waiting
Introduction to Liquibase Rollback
Java Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm
Handling URL Encoded Form Data in Spring REST
Using the Map.Entry Java Class
Java Program to Implement Adjacency List
Vấn đề Nhà sản xuất (Producer) – Người tiêu dùng (Consumer) và đồng bộ hóa các luồng trong Java
Java Program to Find the Nearest Neighbor Using K-D Tree Search
Cài đặt và sử dụng Swagger UI
Dockerizing a Spring Boot Application
Copy a List to Another List in Java
Spring Boot - Google Cloud Platform
Java Program to Implement Levenshtein Distance Computing Algorithm
Java Program to Implement Hopcroft Algorithm
Guide to Guava Multimap
Constructor Injection in Spring with Lombok
Limiting Query Results with JPA and Spring Data JPA
Spring Web Annotations
Predicate trong Java 8
REST Web service: Basic Authentication trong Jersey 2.x
Java Program to implement Array Deque
How to Return 404 with Spring WebFlux
CharSequence vs. String in Java
Java Deep Learning Essentials - Yusuke Sugomori
Introduction to Spring Security Expressions
Converting between an Array and a List in Java
Java – Write an InputStream to a File
How to Set TLS Version in Apache HttpClient
Java Program to Check whether Directed Graph is Connected using BFS
Java Program to Describe the Representation of Graph using Incidence Matrix
Java Program to Implement Bellman-Ford Algorithm
Map Interface trong java