Vérification de la primalité de très grands nombres en Python

Question

Quel serait le moyen le plus rapide de vérifier si un grand nombre donné est premier? Je parle de chiffres d'environ 10^32. J'ai essayé l'algorithme de the great answer by @MarcoBonelli qui est:

from math import sqrt; from itertools import count, islice 

def isPrime(n): 
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1))) 

mais il donne l'erreur de Stop argument for islice() must be None or an integer: 0 <= x <= sys.maxsize lorsqu'il est utilisé contre un si grand nombre. Quelle serait une manière différente, rapide de le faire alors?

Answer 1

Pour un nombre modérément grand, j'utiliserais le test de primalité de Miller-Rabin. Vous pouvez trouver le code Python pour cela ici: https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python

Notez que l'algorithme est de nature probabiliste, mais en l'appliquant un certain nombre de temps vous garantira des réponses correctes avec une très forte probabilité.

Si vous êtes absolument déterminé à utiliser une méthode basée sur une division d'essai, je vous recommande de multiplier un grand nombre de petits nombres premiers et de stocker le nombre composé résultant. Ensuite, vous pouvez prendre le plus grand commun diviseur (GCD) en utilisant un algorithme standard (comme 'fraction.gcd'). Si la réponse n'est pas 1, alors le nombre testé n'est certainement pas premier. Habituellement, vous devez ensuite appliquer le test de Miller-Rabin ci-dessus pour déterminer s'il est premier.

Answer 2

Voici ma mise en œuvre du test de primalité Miller-Rabin; il est par défaut 5 essais aléatoires, mais vous pouvez ajuster cela comme vous le souhaitez. La boucle sur p est un retour rapide pour les petits nombres premiers.

def isPrime(n, k=5): # miller-rabin 
    from random import randint 
    if n < 2: return False 
    for p in [2,3,5,7,11,13,17,19,23,29]: 
     if n % p == 0: return n == p 
    s, d = 0, n-1 
    while d % 2 == 0: 
     s, d = s+1, d/2 
    for i in range(k): 
     x = pow(randint(2, n-1), d, n) 
     if x == 1 or x == n-1: continue 
     for r in range(1, s): 
      x = (x * x) % n 
      if x == 1: return False 
      if x == n-1: break 
     else: return False 
    return True