Description: Miller-Rabin test is a primality test algorithm which determines
whether a given number is prime or not. Implement Miller-Rabin primality test as
given in the text book page 257, Algorithm 7.44. (aN− 1 6= 1 mod N)
Write three functions to answer each of the below questions.
(a) Given a positive integer N, check whether it is prime or not.
1-1• Input: N
• Output: Prime or Not
• For example, Input: 31
• Output: prime
(b) Given a positive integer N, find the smallest prime greater than N.
• Input: N
• Output: M
• Example: Input: 25
• Output: 29
(c) For a composite number, N = 221 (13 ×17), Miller-Rabin test outputs N = 221
as ‘prime’ for a = 174. Such a are known as strong liars. Find all other strong
liars for the N = 221. Similarly, for a = 137 , it shows that N = 221 is composite. Such a’s are known as strong witness of compositeness. Find other strong
witnesses if any.
To Search:
File list (Check if you may need any files):
prob3.py
Download