Vérification de la primalité des 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 nombres de la taille d'environ 10^32. J'ai essayé l'algorithme de la grande réponse de @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 cela donne l'erreur suivante Stop argument for islice() must be None or an integer: 0 <= x <= sys.maxsize lorsqu'il est utilisé contre un si grand nombre de personnes. Quelle serait alors une manière différente et rapide de le faire ?

Answer 1

Voici mon implémentation du test de primalité de Miller-Rabin ; il utilise par défaut 5 essais aléatoires, mais vous pouvez l'ajuster comme vous le souhaitez. La boucle sur p est un retour rapide pour les petites primes.

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

Answer 2

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

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

Si vous tenez absolument à utiliser une méthode basée sur la division d'essai, je vous recommande de multiplier un grand nombre de petits nombres premiers et de stocker le nombre composite obtenu. Vous pouvez ensuite calculer le plus grand diviseur commun (PGCD) à l'aide d'un algorithme standard (tel que 'fraction.gcd'). Si la réponse est différente de 1, alors le nombre testé n'est certainement pas premier. En général, vous appliquerez alors le test de Miller-Rabin ci-dessus pour déterminer s'il est premier.