Java Program to Implement Miller Rabin Primality Test Algorithm

2021 VietMX JAVA 0

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 ** 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:

1
2
3
4
5
6
7
8
9
10
Miller Rabin Primality Algorithm Test
  
Enter number
  
5510389
  
Enter number of iterations
2
  
5510389 is prime

Related posts:

Java Program to Find Second Smallest of n Elements with Given Complexity Constraint
Java Program to Perform Insertion in a 2 Dimension K-D Tree
Spring Cloud – Adding Angular
Tìm hiểu về Web Service
Create a Custom Auto-Configuration with Spring Boot
Quick Guide to java.lang.System
Sắp xếp trong Java 8
Java Program to Perform Preorder Non-Recursive Traversal of a Given Binary Tree
TreeSet và sử dụng Comparable, Comparator trong java
Introduction to Spring Security Expressions
Generating Random Numbers in a Range in Java
An Intro to Spring Cloud Vault
Java Program to Find SSSP (Single Source Shortest Path) in DAG (Directed Acyclic Graphs)
Java Program to Implement Uniform-Cost Search
Java 8 Stream API Analogies in Kotlin
Guide to Spring 5 WebFlux
Converting Java Date to OffsetDateTime
Sort a HashMap in Java
Java Program to Implement Leftist Heap
Spring Boot - Batch Service
Guide to PriorityBlockingQueue in Java
Java Program to Solve the 0-1 Knapsack Problem
Java Program to Generate a Graph for a Given Fixed Degree Sequence
Introduction to Spring Cloud Stream
How to Return 404 with Spring WebFlux
REST Web service: HTTP Status Code và xử lý ngoại lệ RESTful web service với Jersey 2.x
Learning and Improving Algorithm through contests - Antti Laaksonen
Java Program to Check whether Directed Graph is Connected using DFS
Spring Data MongoDB Transactions
Rate Limiting in Spring Cloud Netflix Zuul
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
Spring Boot - OAuth2 with JWT