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程序设计有所帮助。

标签:Python,素数
0
投稿

猜你喜欢

  • Python第三方包之DingDingBot钉钉机器人

    2022-09-06 14:50:38
  • Php+SqlServer实现分页显示

    2023-11-20 05:02:24
  • 基于Python脚本实现邮件报警功能

    2023-02-04 17:16:41
  • python实现将文件夹内的每张图片批量分割成多张

    2023-07-18 17:13:12
  • python网络爬虫之模拟登录 自动获取cookie值 验证码识别的具体实现

    2023-10-08 03:00:37
  • 轻松掌握MySQL数据库锁机制的相关原理

    2008-12-17 15:23:00
  • mysql到oracle的移植

    2011-01-29 16:23:00
  • jquery弹出层背景变暗 Lee dialog

    2008-08-18 13:11:00
  • PHP解析xml格式数据工具类示例

    2023-11-19 20:05:53
  • Perl split字符串分割函数用法指南

    2023-08-13 01:28:36
  • JavaScript解释型模版

    2009-10-19 23:12:00
  • 内容为空时提交如何处理

    2009-07-17 18:25:00
  • 解决python Jupyter不能导入外部包问题

    2021-02-02 06:19:03
  • 设计规范有谱么?

    2008-06-06 12:28:00
  • python实现数据库跨服务器迁移

    2023-09-23 04:54:03
  • 用javascript判断浏览器版本

    2008-04-21 13:50:00
  • AJAX的jQuery实现入门(一)

    2008-05-01 12:55:00
  • Python ConfigParser模块的使用示例

    2023-12-02 03:35:15
  • Python响应对象text属性乱码解决方案

    2023-07-31 13:06:41
  • superLink,让伪链接更有可用性

    2009-06-02 12:35:00
  • asp之家 网络编程 m.aspxhome.com