soft V x e.nyit.edu/bbcswebdav/pid-2403545-dt-content-rid-8010934 2/courses/INCS
ID: 3894591 • Letter: S
Question
soft V x e.nyit.edu/bbcswebdav/pid-2403545-dt-content-rid-8010934 2/courses/INCS 741-VA1-2018SU-VX/Ass1.p 1) Using any programming language of your choice implement the Rabin-Miller algorithm 2) Specifications: The program should take two inputs 1) An integer n 2) t the number of test trails to perform. The program should output "Composite" if n is not an integer and "Inconclusive" if n is most likely an integer, after performing a maximum of t trails. Test 1 1)Set t = 10 for this test 2) Use your code to generate all the prime numbers between 10,000 and 11,000 Provide a screen shot to show your program generating this output 3) Plot a graph showing the number of prime numbers found for the ranges 10,000- 10,100, 10,101 10,200., 10,901 11,000. 4) Discuss any patterns you notice in the graph Test 2 1) Set t-1 for this test 2) Select 10 add, non-prime and positive integers at random 3) Pass these values through you program and note how many return "Inconclusive" 4) Document your results and discuss 1) Submit your code, a detailed readme file (which should explain how to run the code with sample input and output) and a report (which should include your results for Test 1 and Test 2) in a separate files via Blackboard by the due date. No zipped files allowed.Explanation / Answer
import java.util.Scanner;
import java.util.Random;
import java.math.BigInteger;
public class RabinMiller {
public boolean isPrimeNumber(long number, int iteration) {
if (number == 0 || number == 1)
return false;
if (number == 2)
return true;
if (number % 2 == 0)
return false;
long s = number - 1;
while (s % 2 == 0)
s /= 2;
Random random = new Random();
for (int i = 0; i < iteration; i++) {
long r = Math.abs(random.nextLong());
long a = r % (number - 1) + 1, temp = s;
long mod = modPower(a, temp, number);
while (temp != number - 1 && mod != 1 && mod != number - 1) {
mod = mulModules(mod, mod, number);
temp *= 2;
}
if (mod != number - 1 && temp % 2 == 0)
return false;
}
return true;
}
public long modPower(long a, long b, long c) {
long res = 1;
for (int i = 0; i < b; i++) {
res *= a;
res %= c;
}
return res % c;
}
public long mulModules(long a, long b, long mod) {
return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(mod)).longValue();
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
RabinMiller rabinMiller = new RabinMiller();
System.out.println("Enter number");
long num = scan.nextLong();
System.out.println("Enter number of iterations");
int iterate = scan.nextInt();
boolean prime = rabinMiller.isPrimeNumber(num, iterate);
if (prime)
System.out.println( num + " is prime");
else
System.out.println( num + " is composite");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.