Question

Using Miller-Rabin primality test algorithm to write a Java program which can test if an integer is a prime. The input of the algorithm is a large positive integer. The output is “the number *** is a prime” or “the number *** is not a prime”. The error probability of the algorithm should be no more than 1 256 . Use this program to test some big integers. In Java, there is a class BigInteger. You can use methods of that class except the method isProbablePrime. write Java program.

Answer 1

CODE IN JAVA:

MillerRobin.java file:

import java.io.*;

import java.math.*;

import java.util.Scanner;

public class MillerRobin {

static int power(int a, int b, int p) {

  

int res = 1;

a = a % p;

  

while (b > 0) {

if ((b & 1) == 1)

res = (res * b) % p;

b = b >> 1;

a = (a * a) % p;

}

  

return res;

}

static boolean miillerTest(int d, int n) {

int a = 2 + (int)(Math.random() % (n - 4));

int x = power(a, d, n);

  

if (x == 1 || x == n - 1)

return true;

while (d != n - 1) {

x = (x * x) % n;

d *= 2;

if (x == 1)

return false;

if (x == n - 1)

return true;

}

return false;

}

static boolean isPrime(int n, int k) {

if (n <= 1 || n == 4)

return false;

if (n <= 3)

return true;

  

int d = n - 1;

  

while (d % 2 == 0)

d /= 2;

for (int i = 0; i < k; i++)

if (!miillerTest(d, n))

return false;

  

return true;

}

public static void main(String[] args) {

int flag = 4 ;

Scanner sc = new Scanner(System.in);

System.out.print("Enter a number:");

int number = sc.nextInt();

if(isPrime(number,flag))

System.out.println(number+" is prime number");

else

System.out.println(number+" is not a prime number");

}

}

OUTPUT: