文件名称:prob3
介绍说明－－下载内容均来自于网络，请自行研究使用
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.-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.
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.-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.
(系统自动生成,下载前可以参看下载内容)
下载文件列表
prob3.py