2

ポラードの P-1 因数分解を Python で実装しようとしています。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() 関数は 2 乗によるべき乗を使用し、基本的に非常に大きな整数用のスーパーチャージされた pow() です。euc_al_i() は単なる gcd です。好きな gcd() を使用できますが、学習しているので、これらを自分で作成したかったのです。

ここで何がひどく間違っていたのかを突き止めようとしているので、比較的小さな n (20 ビット長ほど) からでも p が見つかりません。

4

2 に答える 2

7

np.prodとsp.uint64が何をするのかはわかりませんが、1974 年に John Pollard によって発明されたp - 1 アルゴリズムについては言えます。

ポラードのアルゴリズムは、フェルマーの小定理a ^ p == a (mod p ) に基づいており、a != 0の場合、a を式で除算することによりa ^ ( p - 1) == 1 (mod p ) と表すことができます。結果として、p - 1 がmを割り算する場合、pは gcd(2^ m - 1, n ) を割ります。ポラードのp - 1 アルゴリズムは、範囲bより小さい整数の最小公倍数としてmを計算します。- 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"

オプションの第 2 段階では、因子を見つけるために第 1 段階の最小公倍数と結合するb1とb2の間の「大きな素数」を検索します。第 2 段階では、累乗剰余ではなく素数ごとの剰余乗算のみが必要なため、非常に高速であり、第 2 段階の 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 なので、1 段階アルゴリズムをb = 120 で呼び出すか、2 段階アルゴリズムをb1 = 50 およびb2 = 120 で呼び出して、因数が見つかるかどうかを確認します。

私のブログで、ポラードのp - 1 因数分解アルゴリズムと、他のいくつかの因数分解アルゴリズムについて説明しています。また、これらの関数の実装に問題がある場合に備えて、powerMod および gcd 関数の実装も提供します。そして、Python でシングルステージ アルゴリズムの簡単な実装を作成しました。http://ideone.com/wdyjxK。

于 2013-05-07T17:23:32.130 に答える