python - 如何找到一个数的最大可能奇数

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。由于这两个数字都是素数，因此该算法只检查奇数。

为了缩短该算法所花费的时间，我想将 N 换成while p < N最大的 64 位奇数，可以乘以N.

EG 一个将N和N_MAX_FACTOR_BITSIZE作为参数并返回其中最大奇数因子的算法N是N_MAX_FACTOR_BITSIZElong。

它返回的数字必须是N_MAX_FACTOR_BITSIZE位长。

任何帮助，将不胜感激。

标签： pythonalgorithmcryptographyprimesfactors

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)