文件名称:prob3
-
所属分类：
- 标签属性：
- 上传时间：2017-05-01
-
文件大小：598byte
-
已下载：0次
-
提 供 者：
-
相关连接：无下载说明：别用迅雷下载，失败请重下，重下不扣分！
介绍说明－－下载内容来自于网络，使用问题请自行百度
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
本网站为编程资源及源代码搜集、介绍的搜索网站，版权归原作者所有！ 粤ICP备11031372号
1999-2046 搜珍网 All Rights Reserved.