Beispiel für die Verwendung von Python zum Erkennen von Primzahlen

In diesem Artikel wird hauptsächlich die Methode der Python-Primzahlerkennung anhand von Beispielen analysiert. Die Details sind wie folgt:

Faktorerkennung:

Erkennungsfaktor, Zeitkomplexität 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

Fermats kleiner Satz:

Wenn n eine Primzahl ist und a eine beliebige positive ganze Zahl kleiner als n ist, dann ist die n-te Potenz von a kongruent mit einem Modulo n

Implementierungsmethode:

Wählen Sie eine Basis (zum Beispiel 2). Wenn 2^(p-1) und 1 nicht modulo p kongruent sind, darf p keine Primzahl sein, andernfalls ist p wahrscheinlich a Primzahl
2**(n-1 )%n ist keine einfach zu berechnende Zahl

Modulo-Operationsregeln:

(a^b) % p = ((a % p)^b) % p
(a * b) % p = (a % p * b % p) % p

Berechnen Sie X^N(% P)

Kann
wenn N eine gerade Zahl ist, dann ist X^N = (X*X)^[N/2]
Wenn N eine ungerade Zahl ist, dann ist 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

Es kann auch wie folgt zusammengefasst werden: Die beiden Funktionen sind gleich

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

Mit der schnellen Verarbeitung der modularen Potenzierungsoperation kann die Fermat-Erkennung realisiert werden

Der Fermat-Test ist genau, wenn eine negative Schlussfolgerung gezogen wird, die positive Schlussfolgerung kann jedoch falsch sein. Er ist sehr effizient große ganze Zahlen, und die Falsch-Positiv-Rate nimmt mit zunehmender Ganzzahl ab

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-Test

Der Miller-Rabin-Test ist derzeit ein weit verbreiteter Test

Quadratischer Erkennungssatz: Wenn p eine Primzahl ist und 0 Fermats kleiner Satz: a^(p-1) ≡ 1(mod p)

Dies ist die Methode des Miller-Rabin-Primzahltests. Extrahieren Sie kontinuierlich den Faktor 2 im Index n-1 und drücken Sie n-1 als d*2^r aus (wobei d eine ungerade Zahl ist). Was wir dann berechnen müssen, ist der Rest von a dividiert durch n hoch d*2^r. Daher ist a^(d * 2^(r-1)) entweder gleich 1 oder gleich n-1. Wenn a^(d * 2^(r-1)) gleich 1 ist, gilt der Satz weiterhin für a^(d * 2^(r-2)) und die Quadratwurzel wird auf diese Weise bis a fortgesetzt ^ ist für ein bestimmtes i (d * 2^i) mod n = n-1 erfüllt oder die 2 im letzten Exponenten wird aufgebraucht, um a^d mod n=1 oder n-1 zu erhalten. Auf diese Weise wird der kleine Satz von Fermat in die folgende Form gebracht:

Extrahieren Sie den Faktor 2 so weit wie möglich und drücken Sie n-1 als d*2^r aus. Wenn n eine Primzahl ist, dann oder a ^d mod n=1, Oder es gibt ein bestimmtes i, so dass a^(d*2^i) mod n=n-1 (0<=i

Theorem: Wenn n eine Primzahl ist und a eine positive ganze Zahl kleiner als n ist, dann basiert der Miller-Test auf a für n wahr sein wird.
Der Miller-Test wird k-mal durchgeführt, die Fehlerwahrscheinlichkeit, zusammengesetzte Zahlen als Primzahlen zu behandeln, wird höchstens 4^(-k) überschreiten

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

Das obige ist der detaillierte Inhalt vonBeispiel für die Verwendung von Python zum Erkennen von Primzahlen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!