如何使用Python檢測素數實例說明

這篇文章主要介紹了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費馬小定理：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

定理:若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中文網其他相關文章！