python - 用 Python 进行费马分解

Question

Python 新手，不确定为什么我的费马因式分解方法会失败？我认为这可能与实现大量数据的方式有关，但我对语言的了解还不足以确定我哪里出错了。

下面的代码在 n=p*q 与 p 和 q 非常接近(如彼此相距大约 20 以内)时有效，但如果它们相距较远，则似乎永远运行。例如，对于 n=991*997，代码可以正常工作并在 <1s 内执行，对于 n=104729*104659 也是如此。但是，如果我将它更改为 n=103591*104659，它就会永远运行(嗯，我让它运行 2 小时然后停止它)。

在正确方向上的任何点将不胜感激!

代码:

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

我在 Wikipedia 上查找了算法这对我有用:

#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)

我尝试了几个测试用例。这个来自维基百科页面:

>>> 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)

这是您的示例案例:

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

查看标记为“Trying”的行表明，在这两种情况下，它收敛得都非常快。

更新:来自评论因素的非常长的整数如下:

n_long=316033277426326097045474758505704980910037958719395560565571239100878192955228495343184968305477308460190076404967552110644822298179716669689426595435572597197633507818204621591917460417859294285475630901332588545477552125047019022149746524843545923758425353103063134585375275638257720039414711534847429265419

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