如何使用Python检测素数实例说明

企鹅博客
企鹅博客
企鹅博客
25193
文章
0
评论
2020年8月31日15:04:32 评论 83 views

这篇文章主要介绍了Python素数检测的方法,实例分析了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检测素数实例说明的详细内容,更多请关注php教程其它相关文章!

继续阅读
企鹅博客
  • 本文由 发表于 2020年8月31日15:04:32
  • 转载请务必保留本文链接:https://www.qieseo.com/341825.html
初步认识Python中的列表与位运算符 php教程

初步认识Python中的列表与位运算符

Python列表 List(列表) 是 Python 中使用最频繁的数据类型。 列表可以完成大多数集合类的数据结构实现。它支持字符,数字,字符串甚至可以包含列表(所谓嵌套)。 列表用< >标识。是py...
新手python用什么版本好? python教程

新手python用什么版本好?

想学习Python的人都会有一个困惑,那就是Python目前有两个版本Python2和Python3,Python2与Python3有何区别,两个版本该学习哪个好呢? python3 和 python...
python中队列的实现方法(代码示例) python教程

python中队列的实现方法(代码示例)

本篇文章给大家带来的内容是关于python中队列的实现方法(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。 对于python来说,要实现一个队列的类根据已经有的方法,是很简...
Python OS模块常用函数说明 python教程

Python OS模块常用函数说明

Python的标准库中的os模块包含普遍的操作系统功能。如果你希望你的程序能够与平台无关的话,这个模块是尤为重要的。即它允许一个程序在编写后不需要任何改动,也不会发生任何问题,就可以在Linux和Wi...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: