3

我的任务是使用费马分解方法分解非常大的合数。这些数字是 1024 位大，大约是 309 个十进制数字。

我想出了下面的 Python 代码，它使用该gmpy2模块来确保准确性。它只是Wikipedia 页面上显示的伪代码的 Python 实现。我阅读了该页面上的“筛选改进”部分，但不确定如何实施。

def fermat_factor(n):
    assert n % 2 != 0  # Odd integers only

    a = gmpy2.ceil(gmpy2.sqrt(n))
    b2 = gmpy2.square(a) - n
    while not is_square(b2):
        a += 1
        b2 = gmpy2.square(a) - n

    factor1 = a + gmpy2.sqrt(b2)
    factor2 = a - gmpy2.sqrt(b2)
    return int(factor1), int(factor2) 

def is_square(n):
    root = gmpy2.sqrt(n)
    return root % 1 == 0  # '4.0' will pass, '4.1212' won't

此代码对于小数字运行得相当快，但对于与问题中给出的数字一样大的数字则需要很长时间。如何提高此代码的速度？我不是在寻找为我编写代码的人，但希望能得到一些建议。感谢您的任何回复。

4

2 回答 2

4

你需要避免做这么多的平方和平方运算，尤其是在大数字上。

避免它们的简单方法是注意 a^2 - N = b^2 必须为真，所有模数才能成为解决方案。例如，

a^2 mod 9 - N mod 9 = b^2 mod 9

假设你的 N 是 55，所以 N mod 9 = 1。

现在考虑 (a mod 9) 的集合，并将其平方，模 9。得到的 a^2 mod 9 是集合：{​​0, 1, 4, 7}。b^2 mod 9 也必须如此。

如果 a^2 mod 9 = 0，则 0 - 1 = 8（所有 mod 9）不是解，因为 8 不是模 9 的平方。这消除了 (a mod 9) = {0, 3 和6}。

如果 a^2 mod 9 = 1，则 1 - 1 = 0（所有 mod 9），因此 (a mod 9) = {1, 8} 是可能的解决方案。

如果 a^2 mod 9 = 4，则 4 - 1 = 3（所有 mod 9）不是可能的解决方案。同上 a^2 mod 9 = 7。

因此，一个模数消除了“a mod 9”的 9 个可能值中的 7 个。

你可以有许多模数，每一个模数都至少消除了一半的可能性。例如，使用一组 10 个模数，您只需检查大约 1,000 个 a 中的 1 个是否是完美平方或具有整数平方根。（我的工作使用了大约 10,000 个模数）。

注意：作为素数幂的模数通常比素数更有用。此外，模数 16 是一个有用的特殊情况，因为当 N mod 4 为 1 时，'a' 必须是奇数，而当 N mod 4 为 3 时，'a' 必须是偶数。“证明留给学生练习。”

于 2013-02-06T08:11:22.513 回答
3

考虑重写此脚本以仅使用整数而不是任意精度浮点数。

gmpy 支持整数平方根（返回平方根的下限，有效计算）。这可以通过测试平方根的平方是否等于原始值来用于 is_square() 函数。

我不确定 gmpy2，但在 gmpy.sqrt() 中需要一个整数参数，并返回一个整数输出。如果您使用浮点数，那么这可能是您的问题（因为与整数相比，浮点数非常慢，尤其是在使用扩展精度时）。如果您实际上使用的是整数，那么每次调用 is_square() 时都必须进行从整数到浮点数的繁琐转换（以及 gmpy2.sqrt() ！= gmpy.sqrt()）。

对于那些一直说这是一个难题的人，请记住，使用这种方法是一个提示：费马分解算法是基于一个弱点，即当要分解的合数有两个接近的质因数时彼此。如果这是作为提示给出的，那么提出问题的实体很可能知道情况就是这样。

编辑：显然， gmpy2.isqrt() 与 gmpy.sqrt() （sqrt 的整数版本）相同，而 gmpy2.sqrt() 是浮点版本。

于 2012-09-26T01:34:29.740 回答