Blogdemaths - Le test de Pépin pour les nombres de Fermat

############################################################
# blogdemaths.wordpress.com
# #########################################################
# Le test de Pépin
# https://blogdemaths.wordpress.com/2016/02/17/nombres-de-fermat-2eme-partie-comment-montrer-que-f7-nest-pas-premier/
# Cet algorithme utilise le test de Pépin pour montrer que
# les nombres de Fermat sont premiers ou non
############################################################

import time

def timing(f):

    def wrap(*args,**kwargs):
        start = time.time()
        resultat = f(*args,**kwargs)
        end = time.time()
        print("Test réalisé en {0:.3f}s\n".format(end-start))
        return None

    return wrap

@timing
def Pepin(n):
    """ Test de Pépin: renvoie True si 3^((F-1)/2) = -1 mod F
        et False sinon """

    F = 2**(2**n)+1 # Nomnbre de Fermat
    a = 3**2 %F # Le modulo F n'est nécéssaire que si 3^2 > F (ce qui est le cas uniquement pour n=1 donc F=5)
    for k in range(2**n-2):
        a = a**2 % F

    if a-F == -1:
        print("F{} est premier.".format(n))
        return True
    else:
        print("F{} n'est pas premier.".format(n))
        return False