Exemple d'utilisation de Python pour détecter les nombres premiers

Cet article présente principalement la méthode de détection des nombres premiers Python. Il analyse les compétences associées à la détection des nombres premiers Python avec des exemples. Les détails sont les suivants :

Détection du facteur :

Facteur de détection, complexité temporelle 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

Petit théorème de Fermat :

Si n est un nombre premier et a est un entier positif inférieur à n, alors la nième puissance de a est congrue à un modulo n

Méthode de mise en œuvre :

Choisissez une base (par exemple 2), pour un grand entier p, si 2^(p-1) et 1 ne sont pas congrus modulo p, alors p ne doit pas être un nombre premier sinon, p est susceptible d'être un ; le nombre premier

2**(n-1 )%n n'est pas un nombre facile à calculer

Règles de fonctionnement modulo :

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

Calculer X^N(% P)

Peut

si N est un nombre pair, alors X^N = (X*X)^[N/2]
Si N est un nombre impair, alors 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

Il peut également être résumé comme l'algorithme suivant Les deux fonctions sont les mêmes

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

Grâce au traitement rapide de l'opération d'exponentiation modulaire, la détection de Fermat peut être réalisée

Le test de Fermat est précis lorsqu'il donne une conclusion négative, mais la conclusion positive peut être fausse. grands entiers, et le taux de faux positifs diminue à mesure que l'entier augmente

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

Test de MILLER-RABIN

Le test de Miller-Rabin est actuellement largement utilisé

Théorème de détection quadratique : si p est un nombre premier et 0 Petit théorème de Fermat : a^(p-1) ≡ 1(mod p)
C'est la méthode du test de primalité de Miller-Rabin. Extrayez continuellement le facteur 2 dans l'index n-1 et exprimez n-1 sous la forme d*2^r (où d est un nombre impair). Ensuite, ce que nous devons calculer devient le reste de a divisé par n à la puissance d*2^r. Par conséquent, a^(d * 2^(r-1)) est soit égal à 1, soit égal à n-1. Si a^(d * 2^(r-1)) est égal à 1, le théorème continue de s'appliquer à a^(d * 2^(r-2)), et la racine carrée se poursuit ainsi jusqu'à ce que a ^ est satisfait pour un certain i (d * 2^i) mod n = n-1 ou le 2 du dernier exposant est utilisé pour obtenir un ^d mod n=1 ou n-1. De cette façon, le petit théorème de Fermat est renforcé sous la forme suivante :

Extraire le facteur 2 autant que possible, et exprimer n-1 sous la forme d*2^r Si n est un nombre premier, alors ou a. ^d mod n=1, Ou il existe un certain i tel que a^(d*2^i) mod n=n-1 (0Théorème : Si n est un nombre premier et a est un entier positif inférieur à n, alors le test de Miller basé sur a pour n sera vrai.

Le test de Miller est effectué k fois, la probabilité d'erreur du traitement des nombres composés comme des nombres premiers ne dépassera pas 4^(-k)

au plus.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!