Python Pollard P-1分解

Question

我正在尝试在Python中实现Pollard的P-1因式分解。请注意，Rho方法有一些答案，但是此p-1是不同的，关于Wiki-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的内置函数是一个无符号的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（）函数通过平方运算使用幂运算，并且对于非常大的整数，基本上是超级pow（）。euc_al_i（）就是gcd。您可以使用任何喜欢的gcd（），但是由于我正在学习，所以我想自己制作这些。

我正在尝试找出错误所在，以至于即使是相对较小的n（小至20位长度）也找不到p。

Answer 1

我不知道np.prod和sp.uint64的作用，但我可以向您介绍一下p -1算法，该算法由约翰·波拉德（John Pollard）于1974年发明。

波拉德的算法是基于费马小定理一个 ^ p == 一个（MOD p），其中，当一个 = 0可以说！一个 ^（p ==（MOD 1 - 1）p除以）一个通过表达。结果，如果p -1除以m，则p除gcd（2 ^ m -1，n）。Pollard的p -1算法将m计算为小于边界b的整数的最小公倍数，因此，如果p的所有因子- 1小于b，则gcd上述（2 ^ LCM（1 .. b） - 1，Ñ）是一个因素Ñ。最小公倍数是通过乘以素数小于计算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之间搜索与第一阶段的最小公倍数组合的“大素数”，以找到一个因数。第二阶段只需要每个素数的模乘法，而无需模幂，因此相当快，第二阶段gcd可以分批计算。缓存很小，但对功能效率很重要。

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 -1 的b调用Pollard方法。例如，如果要分解n = 87463 = 149 * 587，请注意n -1 = 87462 = 2 * 3 * 3 * 43 * 113，因此调用b = 120 的一阶段算法或b1 = 50和b2 = 120 的两阶段算法，看看是否找到因数。

我在博客上讨论了Pollard的p -1分解算法以及其他几种分解算法。我还提供了powerMod和gcd函数的实现，以防万一您无法实现这些功能。然后，我在Python的上编写了单阶段算法的简单实现http://ideone.com/wdyjxK。