Fermat Factoring Method.sagews

def isqrt(n):
    return int(floor(sqrt(n)))

def usqrt (n):
    ur = isqrt(n)
    if ur ** 2 < n:
        ur = ur + 1
    return(ur)

def FermatAttack (n, rounds):
    st = usqrt(n)
    for x in range(st, st + rounds + 1):
        sq = x ** 2 - n
        y = isqrt(sq)
        if y ** 2 == sq:
            print "Factor found in round {0}".format(x - st +1)
            return ZZ(x+y)
    print "No factor found in {0} rounds".format(rounds)

R=159036514693689983941651127883368586201655747927706116369962006335777320438442666570787646792828597134996921334192059514888059653595070079977594119733157812587889
R
p=FermatAttack(R,1000)

159036514693689983941651127883368586201655747927706116369962006335777320438442666570787646792828597134996921334192059514888059653595070079977594119733157812587889 Factor found in round 1 398793824793827498330928302913021803284598743957843985738927598759843759843750179

q=R/p
print'The primes factors of R are',p 
print'and',q

The primes factors of R are 398793824793827498330928302913021803284598743957843985738927598759843759843750491 and 398793824793827498330928302913021803284598743957843985738927598759843759843750179