如何找到一个数的最大可能奇数因子

Question

我正在编写脚本来破解小型 RSA 密钥。我想到了一种方法，可以在我正在使用的方法中节省大量时间。为此，我需要知道如何找到特定大小的数字的最大可能质因数。例如：

N = 9868690954602957859
N_MAX_FACTOR_BITSIZE = 64

然后，我运行N通过这个算法：

p = floor(sqrt(n))
if p mod 2 == 0:
    p += 1
while p < N:  # Referenced above
    if p mod n == 0:
        return p
    p += 2

该算法的工作原理是，只有 floor(sqrt(N)) 以上的两个质数会平分 N。由于两个数都是素数，因此该算法只检查奇数。

为了缩短这个算法的时间，我想把while p < N中的N换成能乘以N的最大奇数64位数。

EG 一种算法，它以 N 和 N_MAX_FACTOR_BITSIZE 作为参数，returns N 的最大奇数因子，即 N_MAX_FACTOR_BITSIZE 长。

它 returns 的数字必须 N_MAX_FACTOR_BITSIZE 位长。

如有任何帮助，我们将不胜感激。

Answer 1

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors

n = 9868690954602957859

primes =prime_factors(n)[-1]

print(primes)

如何找到一个数的最大可能奇数因子

How to find the largest possible odd factor of a number

python

algorithm

primes

cryptography

factors