Python Pollard P-1 分解

Question

我正在尝试在 Python 中实现 Pollard 的 P-1 分解。请注意，Rho 方法有一些答案，但这个 p-1 是不同的，关于 p-1，我能给你的最好的是 wiki 和 Wolfram:

http://en.wikipedia.org/wiki/Pollard 's_p_%E2%88%92_1_algorithm

http://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html

这是从 n 中分解某些东西，但一直找不到 p。 np 和 sp 分别来自 numpy 和 scipy。所以 sp.uint64 的内置函数是一个 unsigned long 64 int(因为预期整数的大小)并且 np.prod(p) 是列表 p 的累积乘积 pi:

def pm1_attack(n,b):
  p = [2,3,5,7,11,13,17]; i=19; a=2
  while i<b:
    if is_prime(i,10): p.append(i)
    i+=2;
  k = sp.uint64(np.prod(p)); q = power2(a,k,n)
  g = euc_al_i((q-1),n)
  print "product pi: ",k
  print "q: ",q
  print "g: ",g
  #return a

print "pollard_pm1_attack(n,b): ",pollard_pm1_attack(n,2000)

输出没有找到p:

Python 2.7 (r27:82525, Jul  4 2010, 09:01:59) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
p = 1300199 
q = 2063507 

euler_totient = 2682966374188 

common n = 2682969737893 


public key e = 1588051820871 

secret key d = 2410616084843 

cleartext message = test 

encoded message = 1489995542681 

decoded message = test 

check_rsa = Successful encryption and decrytion. Message is authenticated. 

pollard_pm1_attack(n,b):  product pi:  18446744073460481730
q:  2391570546599
g:  1
None
>>> 

我正在学习 Python，所以这可能是一些简单的错误。 power2() 函数通过平方使用求幂，基本上是对非常大的整数进行 super 充电的 pow()。 euc_al_i() 只是 gcd。您可以使用任何您喜欢的 gcd()，但由于我正在学习，所以我想自己制作这些。

我试图找出这里出了什么可怕的错误，即使是相对较小的 n(小到 20 位长度)也找不到 p。

Answer 1

我不知道np.prod 和sp.uint64 是做什么的，但我可以告诉你p - 1 算法，由 John Pollard 于 1974 年发明。

波拉德算法基于费马小定理 a ^ p == a (mod p),当 a != 0 可以表示为 a ^ (p - 1) == 1 (mod p ) 通过将 a 除以表达式。因此，如果 p - 1 整除 m，则 p 整除 gcd(2^m - 1， n)。 Pollard 的 p - 1 算法将 m 计算为小于边界 b 的整数的最小公倍数，因此如果 b 的所有因子em>p - 1 小于 b，则 gcd(2 ^ lcm(1..b) - 1, n) 是 n 的因数。最小公倍数的计算方法是将小于 b 的素数乘以它们小于 b 的重数:

function pminus1(n, b)
    c := 2
    for p in primes(b)
        pp := p
        while pp < b
            c := powerMod(c, p, n)
            pp := pp * p
    g := gcd(c-1, n)
    if 1 < g < n return g
    error "factorization failed"

可选的第二阶段搜索 b1 和 b2 之间的“大素数”，它与第一阶段的最小公倍数结合以找到一个因子。第二阶段只需要对每个素数进行模乘而不是模幂运算，速度非常快，并且可以批量计算第二阶段的gcds。缓存虽小，但对功能的效率很重要。

function pminus1(n, b1, b2)
    c := 2
    for p in primes(b1)
        pp := p
        while pp < b
            c := powerMod(c, p, n)
            pp := pp * p
    g := gcd(c-1, n)
    if 1 < g < n return g
    k := 0
    for q in primes(b1, b2)
        d := q - p
        if d is not in cache
            x := powerMod(c, d, n)
            store d, x in cache
        c := (c * x(d)) % n
        p := q
        k := k + 1
        if k % 100 == 0
            g := gcd(c-1, n)
            if 1 < g < n return g
    g := gcd(c-1, n)
    if 1 < g < n return g
    error "factorization failed"

Pollard 的p - 1 方法可能找不到n 的一个因子；这取决于 n - 1 的因式分解和您选择的边界。检查的方法是自己分解n - 1，然后用大于n的最大因子的b调用Pollard的方法 - 1. 例如，如果你想分解 n = 87463 = 149 * 587，请注意 n - 1 = 87462 = 2 * 3 * 3 * 43 * 113，所以调用 b = 120 的单阶段算法或 b1 = 50 和 b2 = 120 的两阶段算法，看看你是否找到一个因素。

我在 my blog 讨论了 Pollard 的 p - 1 分解算法，以及其他几种分解算法。 .我还提供了 powerMod 和 gcd 函数的实现，以防您在实现这些函数时遇到问题。我用 Python 在 上写了一个简单的单阶段算法实现。 http://ideone.com/wdyjxK .