Python素数检测的方法
作者:蛇小狼 发布时间:2021-02-13 13:07:30
本文实例讲述了Python素数检测的方法。分享给大家供大家参考。具体如下:
因子检测:
检测因子,时间复杂度O(n^(1/2))
def is_prime(n):
if n < 2:
return False
for i in xrange(2, int(n**0.5+1)):
if n%i == 0:
return False
return True
费马小定理:
如果n是一个素数,a是小于n的任意正整数,那么a的n次方与a模n同余
实现方法:
选择一个底数(例如2),对于大整数p,如果2^(p-1)与1不是模p同余数,则p一定不是素数;否则,则p很可能是一个素数
2**(n-1)%n 不是一个容易计算的数字
模运算规则:
(a^b) % p = ((a % p)^b) % p
(a * b) % p = (a % p * b % p) % p
计算X^N(% P)
可以
如果N是偶数,那么X^N =(X*X)^[N/2];
如果N是奇数,那么X^N = X*X^(N-1) = X *(X*X)^[N/2];
def xn_mod_p(x, n, p):
if n == 0:
return 1
res = xn_mod_p((x*x)%p, n>>1, p)
if n&1 != 0:
res = (res*x)%p
return res
也可以归纳为下面的算法 两个函数是一样的
def xn_mod_p2(x, n, p):
res = 1
n_bin = bin(n)[2:]
for i in range(0, len(n_bin)):
res = res**2 % p
if n_bin[i] == '1':
res = res * x % p
return res
有了模幂运算快速处理就可以实现费马检测
费马测试当给出否定结论时,是准确的,但是肯定结论有可能是错误的,对于大整数的效率很高,并且误判率随着整数的增大而降低
def fermat_test_prime(n):
if n == 1:
return False
if n == 2:
return True
res = xn_mod_p(2, n-1, n)
return res == 1
MILLER-RABIN检测
Miller-Rabin检测是目前应用比较广泛的一种
二次探测定理:如果p是一个素数,且0<x<p,则方程x^2%p=1的解为:x=1或x=p-1
费马小定理:a^(p-1) ≡ 1(mod p)
这就是Miller-Rabin素性测试的方法。不断地提取指数n-1中的因子2,把n-1表示成d*2^r(其中d是一个奇数)。那么我们需要计算的东西就变成了a的d*2^r次方除以n的余数。于是,a^(d * 2^(r-1))要么等于1,要么等于n-1。如果a^(d * 2^(r-1))等于1,定理继续适用于a^(d * 2^(r-2)),这样不断开方开下去,直到对于某个i满足a^(d * 2^i) mod n = n-1或者最后指数中的2用完了得到的a^d mod n=1或n-1。这样,Fermat小定理加强为如下形式:
尽可能提取因子2,把n-1表示成d*2^r,如果n是一个素数,那么或者a^d mod n=1,或者存在某个i使得a^(d*2^i) mod n=n-1 ( 0<=i<r ) (注意i可以等于0,这就把a^d mod n=n-1的情况统一到后面去了)
定理:若n是素数,a是小于n的正整数,则n对以a为基的Miller测试,结果为真.
Miller测试进行k次,将合数当成素数处理的错误概率最多不会超过4^(-k)
def miller_rabin_witness(a, p):
if p == 1:
return False
if p == 2:
return True
#p-1 = u*2^t 求解 u, t
n = p - 1
t = int(math.floor(math.log(n, 2)))
u = 1
while t > 0:
u = n / 2**t
if n % 2**t == 0 and u % 2 == 1:
break
t = t - 1
b1 = b2 = xn_mod_p2(a, u, p)
for i in range(1, t + 1):
b2 = b1**2 % p
if b2 == 1 and b1 != 1 and b1 != (p - 1):
return False
b1 = b2
if b1 != 1:
return False
return True
def prime_test_miller_rabin(p, k):
while k > 0:
a = randint(1, p - 1)
if not miller_rabin_witness(a, p):
return False
k = k - 1
return True
希望本文所述对大家的Python程序设计有所帮助。
猜你喜欢
- 我们可以利用err对象来判断。当程序没有出现错误就说明已经执行了sql操作: sql="insert into
- 首先这个是7米当时问我一个问题,不过可惜我不知道怎么解决,后来知道解决方法很简单,只是添加了一个margin-top:-1em就
- Embedding词嵌入在 pytorch 中非常简单,只需要调用 torch.nn.Embedding(m, n) 就可以了,m 表示单词
- 今天主要向大家讲述的是优化SQL Server数据库的实际操作经验的总结,同时也有对其优化的实际操作中出现的一些问题的描述,以及对SQL S
- 本文实例讲述了php简单实现批量上传图片的方法。分享给大家供大家参考,具体如下:<?phpfunction upload_multi(
- 根据我最近的一些实践以及在和一些读者进行关于HTML表格的使用问题沟通之后,决定写这篇文章。总的来说,我注意到由于误导性信息,他们对于tab
- 环境Python 3.7.4pymysql8.0.11 MySQL Community Server读取图片以二进制格式读取图片with o
- 流动网页设计有很多好处,但也只有在正确使用的时候。合适的技巧会使页面在大屏幕、小屏幕抑、PDA小屏幕上都能得到良好的呈现。但是,糟糕的代码结
- 本文实例讲述了Python栈的实现方法。分享给大家供大家参考,具体如下:Python实现栈栈的数组实现:利用python列表方法代码如下:#
- 目录正文开始1. DRF 中的限流2. 限流进阶配置3. 限流思路分析4. 源码分析5. 其它注意事项参考资料正文开始先说一个限流这个概念,
- 在python项目中,我们经常会用到lambda,那么lambda是什么呢,有什么作用,下面我们开始介绍1、可以使用lambda关键字创建匿
- 原来工作中曾经碰到过UL列表里一些异常的表现,加上昨天看到了http://bbs.blueidea.com/thread-2984871-1
- 我的工作内容可以说是五花八门,策划、文案、设计(包括平面设计、网站设计、VIS设计)、前端代码、交互、测试、摄影、项目管理等。所有这些工作最
- 随着网络技术的不断发展,网络应用已经渗透到人类社会的各个角落。作为网络世界的支撑点的网站,更是人们关注的热点:政府利用网站宣传自己的施政纲领
- Python可以使用 xml.etree.ElementTree 模块从简单的XML文档中提取数据。 为了演示,假设你想解析Planet P
- 1.嵌入 IFrame(/assets/img/anchor.svg)]()](https://gradio.app/sharing-you
- 近期,MSN、江民等知名网站相继受到了黑客的威胁和攻击,一时间网络上风声鹤唳。本报编辑部接到本文作者(炽天使)的电话,他详细讲述了发现国内最
- 以下摘录自 oreilly.JavaScript.The.Definitive.Guide.5th.Edition.Aug.200
- 导言:到目前为止,我们的教程围绕的是text数据。然而,很多应用程序既需要处理text数据,也需要处理二进制数据。比如招聘网站可能需要用户上
- 当数据库服务器变得十分繁忙导致性能下降时,你会怎么办?购买更多的硬件升级你的服务器,还是重新考虑数据库服务器设计使得数据库平台具备良好的可升