Python Pollard P1因子分解

2024-03-28 18:27:05 发布

您现在位置:Python中文网/ 问答频道 /正文

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

http://en.wikipedia.org/wiki/Pollard的算法

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

这是从n中分解一些东西,但始终没有找到p。np和sp分别来自numpy和scipy。因此,sp.uint64的内置函数是一个无符号的长64整数(因为预期整数的大小),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。


Tags: 函数答案httpmessagenpwikipi整数
2条回答

下面是用python实现的两阶段版本。

from math import gcd, log

def pminus1(n, B1, B2):
    log_B1 = log(B1)
    M = 1
    primes = prime_sieve()
    for p in primes:
        if p > B1:
            break
        M *= p**int(log_B1/log(p))
    M = pow(2, M, n)
    g = gcd(M-1, n)
    if 1 < g < n:
        return True
    if g == n:
        return False

    # Start part 2.
    cache = {0:M}
    S = (M*M) % n
    for d in range(2, int(log(B2)**2), 2):
        cache[d] = cache[d-2] * S) % n

    HQ = M
    for k, q in enumerate(primes):
        if q > B2:
            break
        d = q - p
        HQ = (HQ * cache[d]) % n
        M = (M * (HQ-1)) % n
        p = q
        if k % 200 == 0:
            if 1 < gcd(M, n) < n:
                return True
    return 1 < gcd(M, n) < n

我不知道np.prodsp.uint64是做什么的,但是我可以告诉你p-1算法,它是由John Pollard在1974年发明的。

Pollard的算法是基于Fermat的小定理a^p==a(modp),当a时!=0可以用表达式除以a^(p-1)==1(modp)。因此,如果p-1除m,则p除gcd(2^m-1,n)。Pollard'sp-1算法将m计算为小于a界b的整数的最小公倍数,因此如果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"

可选的第二阶段搜索b1b2之间的“大素数”,该素数与第一阶段的最小公倍数结合以找到因子。第二阶段只需要对每个素数进行模乘,而不是模幂运算,因此运算速度相当快,第二阶段的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的因子分解和您选择的界限。检查的方法是自己设置factorn-1,然后使用大于最大factorn-1的ab调用Pollard的方法。例如,如果您想要factorn=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编写了一个单阶段算法的简单实现。

相关问题 更多 >