Blogdemaths - Méthode de factorisation de Fermat

#
# blogdemaths.wordpress.com
#
#
# Algorithme de factorisation de Fermat
#

import math

# Entier à factoriser
N=100895598169

#Initialisation
q=int(math.sqrt(N))
a=q+1
deuxaplusun = 2*a+1
diff = a**2 - N

# Nombre d'étapes
compteur = 1

while not (  int(math.sqrt(diff))**2 == diff ): # Tant que a^2 - N n'est pas un carré
    diff += deuxaplusun
    a += 1
    deuxaplusun += 2
    compteur += 1

b=int(math.sqrt(diff))

print("Le nombre {0} est le produit de {1} par {2}.".format(N,a+b,a-b))
print("Il a fallu {0} étapes pour le factoriser.".format(compteur))