我已经编写了这段代码(在python中),用于分解质数中的整数(费马定理)。

#!/usr/bin/python2

import random,math


n=590632926550117049

a=math.ceil(math.sqrt(n))
b2=a*a-n

while math.sqrt(b2)!=math.floor(math.sqrt(b2)):
    a=a+1
    b2=a*a-n

b=math.sqrt(b2)

p=a+b
q=a-b

print("p =",p)
print("q =",q)


数字n = 590632926550117049是57848543 * 10209987943的乘积,但我的程序返回:1156469901 * 510720535。为什么呢

编辑:即用187或15或其他数字可以正常工作。

最佳答案

math.sqrt()使用标准IEEE 64位值。它只能精确计算小于2 ** 53的参数。您的n值大于该值。

如果要为大数提供精确的整数平方根,建议使用gmpy2

免责声明:我维护gmpy2。

编辑:这是您的程序的更新版本。

import gmpy2

n = 590632926550117049

a = gmpy2.isqrt(n) + 1
b2 = a * a - n

while not gmpy2.is_square(b2):
    a = a + 1
    b2 = a * a - n

b = gmpy2.isqrt(b2)

p = a + b
q = a - b

print("p =", p)
print("q =", q)

关于python - Fermat分解不起作用(Python),我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/27695772/

10-12 19:34