Question

Write a computer program that implements the Miller–Rabin algorithm for a user-specified n. The program should allow the user two choices: (1) specify a possible
witness to test using the Witness procedure or (2) specify a number s of random witnesses for the Miller–Rabin test to check. Python or C. Sorry to be picky just eaiser to read.

Answer 1

----------------------------------------------------------------------------------------------------

// Screenshot of python code

import random def powerMod(a, d, n): if d == 1: return a % n elif d == 0: return 1 else: x = powerModa, d >> 1, n) if d % 2 == 0: return (x*x) % n else: return (a*x*x) % n

def millerRabinTest(n, d, option): if option == 1: a = int(input("Enter a possible witness 'a' for the miller-rabin test: ")) else: a = random.randint(2, n-2) x = powerMod(a, d, n) if x == 1 or x == n-1: return True while d != n-1: x = (x*x)% n d = 0*2 if x == n-1: return True if x == 1: return false return false

def isPrime(n, s, option): if n <= 1 or n == 4: return false if n <= 3: return True d = n-1 while d % 2 == 0: d = d//2 for i in range(s): if not millerRabinTest(n, d, option): return false return True

n = int(input("Enter a number 'n' to check whether it's a prime: ")) print("1. Select <1> if you want to specify a possible witness to test during witness procedure.") print("2. Select <2> if you want to specify a number 's' of random witnesses for miller-rabin test.") option = int(input("Enter either 1 or 2: ")) if option == 2: S = int(input("Enter the number of witnesses (s > 0) for miller-rabin test: ")) else: # select s to be a random number number between 2 and n S = random.randint(2, n) 62 if isPrime(n, s, option): print(str(n) + " is prime") else: print(str(n) + " is composite") 67 68

----------------------------------------------------------------------------------------------------

Lule d umber '1' to check whether it's a prime: 2007 1. Select <1> if you want to specify a possible witness to test during witness procedure. 2. Select <2> if you want to specify a number 's' of random witnesses for miller-rabin test. Enter either 1 or 2: 1 Enter a possible witness 'a' for the miller-rabin test: Enter a possible witness 'a' for the miller-rabin test: Enter a possible witness 'a' for the miller-rabin test: 2047 is composite

Enter a number 'n' to check whether it's a prime: 12 1. Select <1> if you want to specify a possible witness to test during witness procedure. 2. Select <2> if you want to specify a number 's' of random witnesses for miller-rabin test. Enter either 1 or 2: 2 Enter the number of witnesses (3 > 0) for miller-rabin test: 127 is prime