SHARE
TWEET

Blogdemaths - Méthode de factorisation de Fermat

Blogdemaths May 17th, 2014 435 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #
  2. # blogdemaths.wordpress.com
  3. #
  4. #
  5. # Algorithme de factorisation de Fermat
  6. #
  7.  
  8. import math
  9.  
  10. # Entier à factoriser
  11. N=100895598169
  12.  
  13. #Initialisation
  14. q=int(math.sqrt(N))
  15. a=q+1
  16. deuxaplusun = 2*a+1
  17. diff = a**2 - N
  18.  
  19. # Nombre d'étapes
  20. compteur = 1
  21.  
  22. while not (  int(math.sqrt(diff))**2 == diff ): # Tant que a^2 - N n'est pas un carré
  23.     diff += deuxaplusun
  24.     a += 1
  25.     deuxaplusun += 2
  26.     compteur += 1
  27.  
  28. b=int(math.sqrt(diff))
  29.  
  30. print("Le nombre {0} est le produit de {1} par {2}.".format(N,a+b,a-b))
  31. print("Il a fallu {0} étapes pour le factoriser.".format(compteur))
RAW Paste Data
Top