Fermat Factorisation with Python

Question

New to Python and not sure why my fermat factorisation method is failing? I think it may have something to do with the way large numbers are being implemented but I don't know enough about the language to determine where I'm going wrong.

The code below works when n=p*q is made with p and q extremely close (as in within about 20 of each other) but seems to run forever if they are further apart. For example, with n=991*997 the code works correctly and executes in <1s, likewise for n=104729*104659. If I change it ton=103591*104659 however, it just runs forever (well, I let it go 2 hours then stopped it).

Any points in the right direction would be greatly appreciated!

Code:

import math

def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

n=103591*104729

a=isqrt(n) + 1
b2=a*a - n
b=isqrt(b2)

while b*b!=b2:
  a=a+1
  b2=b2+2*a+1
  b=isqrt(b2)

p=a+b
q=a-b

print('a=',a,'\n')
print('b=',b,'\n')
print('p=',p,'\n')
print('q=',q,'\n')
print('pq=',p*q,'\n')
print('n=',n,'\n')
print('diff=',n-p*q,'\n')

Answer 1

I looked up the algorithm on Wikipedia and this works for me:

#from math import ceil

def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

def fermat(n, verbose=True):
    a = isqrt(n) # int(ceil(n**0.5))
    b2 = a*a - n
    b = isqrt(n) # int(b2**0.5)
    count = 0
    while b*b != b2:
        if verbose:
            print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2) # int(b2**0.5)
        count += 1
    p=a+b
    q=a-b
    assert n == p * q
    print('a=',a)
    print('b=',b)
    print('p=',p)
    print('q=',q)
    print('pq=',p*q)
    return p, q

n=103591*104729
fermat(n)

I tried a couple test cases. This one is from the wikipedia page:

>>> fermat(5959)
Trying: a=78 b2=125 b=11
Trying: a=79 b2=282 b=16
a= 80
b= 21
p= 101
q= 59
pq= 5959
(101, 59)

This one is your sample case:

>>> fermat(103591*104729)
Trying: a=104159 b2=115442 b=339
a= 104160
b= 569
p= 104729
q= 103591
pq= 10848981839
(104729, 103591)

Looking at the lines labeled "Trying" shows that, in both cases, it converges quite quickly.

UPDATE: Your very long integer from the comments factors as follows:

n_long=316033277426326097045474758505704980910037958719395560565571239100878192955228495343184968305477308460190076404967552110644822298179716669689426595435572597197633507818204621591917460417859294285475630901332588545477552125047019022149746524843545923758425353103063134585375275638257720039414711534847429265419

fermat(n_long, verbose=False)
a= 17777324810733646969488445787976391269105128850805128551409042425916175469326288448917184096591563031034494377135896478412527365012246902424894591094668262
b= 157517855001095328119226302991766503492827415095855495279739107269808590287074235
p= 17777324810733646969488445787976391269105128850805128551409042425916175469483806303918279424710789334026260880628723893508382860291986009694703181381742497
q= 17777324810733646969488445787976391269105128850805128551409042425916175469168770593916088768472336728042727873643069063316671869732507795155086000807594027
pq= 316033277426326097045474758505704980910037958719395560565571239100878192955228495343184968305477308460190076404967552110644822298179716669689426595435572597197633507818204621591917460417859294285475630901332588545477552125047019022149746524843545923758425353103063134585375275638257720039414711534847429265419

Answer 2

The error was doing the addition after incremeting a so the new value was not the square of a. This works as intended :

while b*b!=b2:
  b2+=2*a+1  
  a=a+1  
  b=isqrt(b2)

for big numbers it should be faster than computing the square which has quite a greater number of digits.