我已经编写了这段代码(在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 - 费马分解不起作用(python),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27695772/