Blogdemaths

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

Feb 17th, 2016
242
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ############################################################
  2. # blogdemaths.wordpress.com
  3. # #########################################################
  4. # Le test de Pépin
  5. # https://blogdemaths.wordpress.com/2016/02/17/nombres-de-fermat-2eme-partie-comment-montrer-que-f7-nest-pas-premier/
  6. # Cet algorithme utilise le test de Pépin pour montrer que
  7. # les nombres de Fermat sont premiers ou non
  8. ############################################################
  9.  
  10. import time
  11.  
  12. def timing(f):
  13.    
  14.     def wrap(*args,**kwargs):
  15.         start = time.time()
  16.         resultat = f(*args,**kwargs)
  17.         end = time.time()
  18.         print("Test réalisé en {0:.3f}s\n".format(end-start))
  19.         return None
  20.  
  21.     return wrap
  22.  
  23. @timing
  24. def Pepin(n):
  25.     """ Test de Pépin: renvoie True si 3^((F-1)/2) = -1 mod F
  26.        et False sinon """
  27.  
  28.     F = 2**(2**n)+1 # Nomnbre de Fermat
  29.     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)
  30.     for k in range(2**n-2):
  31.         a = a**2 % F
  32.  
  33.     if a-F == -1:
  34.         print("F{} est premier.".format(n))
  35.         return True
  36.     else:
  37.         print("F{} n'est pas premier.".format(n))
  38.         return False
RAW Paste Data