対数に対するポラードのローアルゴリズム

対数に対するポラードのローアルゴリズムは、離散対数問題を解決するために 1978 年にジョン ポラードによって導入されたアルゴリズムであり、整数因数分解問題を解決するポラードのローアルゴリズムに類似しています。

目標は、が によって生成された巡回群に属するような を計算することです。アルゴリズムは、と なる整数、、、を計算します。基礎となる群がの位数の巡回である場合、を として代入し、2 つの累乗が等しいのは、指数が底の位数（この場合は を法として）を法として等しい場合のみであることに注意すると、 は方程式 の解の 1 つになります。この方程式の解は、拡張ユークリッドの互除法を使用して簡単に得られます。 ${\displaystyle \gamma}$${\displaystyle \alpha ^{\gamma }=\beta }$${\displaystyle \beta}$ ${\displaystyle G}$${\displaystyle \alpha}$ ${\displaystyle a}$${\displaystyle b}$${\displaystyle A}$${\displaystyle B}$${\displaystyle \alpha^{a}\beta^{b}=\alpha^{A}\beta^{B}}$ ${\displaystyle n}$${\displaystyle \beta}$${\displaystyle {\alpha }^{\gamma }}$${\displaystyle n}$${\displaystyle \gamma}$${\displaystyle (Bb)\gamma =(aA){\pmod {n}}}$

必要な、、、 を見つけるために、アルゴリズムはフロイドのサイクル検出アルゴリズムを使用してシーケンス 内のサイクルを検出します。ここで、関数 はランダムに見えるものと想定されるため、ステップの後におおよその長さのループに入る可能性があります。 このような関数を定義する 1 つの方法は、次の規則を使用することです。ハッシュ関数を使用して、ほぼ同じサイズの3 つの互いに素な部分集合、、に分割します。がに含まれる場合は、と の両方を 2 倍にします。 の場合は を増分し、の場合は を増分します。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}}$ ${\displaystyle f:x_{i}\mapsto x_{i+1}}$${\displaystyle {\sqrt {\frac {\pi n}{8}}}}$${\displaystyle {\sqrt {\frac {\pi n}{8}}}}$ ${\displaystyle G}$ ${\displaystyle S_{0}}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle x_{i}}$${\displaystyle S_{0}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle x_{i}\in S_{1}}$${\displaystyle a}$${\displaystyle x_{i}\in S_{2}}$${\displaystyle b}$

を位数の巡回群とし、を分割として、写像を ${\displaystyle G}$${\displaystyle n}$${\displaystyle \alpha ,\beta \in G}$${\displaystyle G=S_{0}\cup S_{1}\cup S_{2}}$${\displaystyle f:G\to G}$

${\displaystyle f(x)={\begin{cases}\beta x&x\in S_{0}\\x^{2}&x\in S_{1}\\\alpha x&x\in S_{2}\end{cases}}}$

そして地図を定義し 、${\displaystyle g:G\times \mathbb {Z} \to \mathbb {Z} }$${\displaystyle h:G\times \mathbb {Z} \to \mathbb {Z} }$

${\displaystyle {\begin{aligned}g(x,k)&={\begin{cases}k&x\in S_{0}\\2k{\pmod {n}}&x\in S_{1}\\k+1{\pmod {n}}&x\in S_{2}\end{cases}}\\h(x,k)&={\begin{cases}k+1{\pmod {n}}&x\in S_{0}\\2k{\pmod {n}}&x\in S_{1}\\k&x\in S_{2}\end{cases}}\end{aligned}}}$

入力:  a : G
       の生成元b : G
の要素出力: a x = bとなる整数x、または失敗
i ← 0、a 0 ← 0、b 0 ← 0、x 0 ← 1 ∈ G
を初期化します。


    i ← i + 1をループする

    x i ← f ( x i −1 )
     、a i ← g ( x i −1、a i −1 )
     、 bi ← h ( x i −1、bi −1 )

    x 2 i −1 ← f ( x 2 i −2 )、
     a 2 i −1 ← g ( x 2 i −2、a 2 i −2 )、
     b 2 i −1 ← h ( x 2 i −2、b 2 i −2 )
     x 2 i ← f ( x 2 i −1 )、
     a 2 i ← g ( x 2 i −1、a 2 i −1 )、
     b 2 i ← h ( x 2 i −1、b 2 i −1 )
ただし x i ≠ x 2 i

r ← b i − b 2 i
 r = 0の場合失敗を返す
r −1 ( a 2 i − a i ) mod nを返す 

たとえば、2 を法として生成されるグループを考えます(グループの順序は、2 は 1019 を法として単位のグループを生成します)。アルゴリズムは次のC++プログラムによって実装されます。 ${\displaystyle N=1019}$${\displaystyle n=1018}$

#include <stdio.h> 

const int n = 1018 , N = n + 1 ; /* N = 1019 -- 素数 */ const int alpha = 2 ; /* ジェネレータ */ const int beta = 5 ; /* 2^{10} = 1024 = 5 (N) */           
                
                 

void new_xab ( int & x , int & a , int & b ) { switch ( x % 3 ) { case 0 : x = x * x % N ; a = a * 2 % n ; b = b * 2 % n ; break ; case 1 : x = x * alpha % N ; a = ( a + 1 ) % n ; break ; case 2 : x = x * beta % N ; b = ( b + 1 ) % n ; break ; } }       
      
                                
                                  
                                   
  


int main ( void ) { int x = 1 , a = 0 , b = 0 ; int X = x , A = a , B = b ; for ( int i = 1 ; i < n ; ++ i ) { new_xab ( x , a , b ); new_xab ( X , A , B ); new_xab ( X , A , B ); printf ( "%3d %4d %3d %3d %4d %3d %3d \n " , i , x , a , b , X , A , B ); if ( x == X ) break ; } return 0 ; }  
           
           
           
      
      
      
           
        
  
   

結果は次のとおりです（編集済み）。

イクアブ
------------------------------
 1 2 1 0 10 1 1
 2 10 1 1 100 2 2
 3 20 2 1 1000 3 3
 4 100 2 2 425 8 6
 5 200 3 2 436 16 14
 6 1000 3 3 284 17 15
 7 981 4 3 986 17 17
 8 425 8 6 194 17 19
...................................
48 224 680 376 86 299 412
49 101 680 377 860 300 413
50 505 680 378 101 300 415
51 1010 681 378 1010 301 416

つまり、であり、 に対しては が予想どおりの解です。は素数ではないので、 に対しては別の解 が存在し、 が成り立ちます。 ${\displaystyle 2^{681}5^{378}=1010=2^{301}5^{416}{\pmod {1019}}}$${\displaystyle (416-378)\gamma =681-301{\pmod {1018}}}$${\displaystyle \gamma _{1}=10}$${\displaystyle n=1018}$${\displaystyle \gamma _{2}=519}$${\displaystyle 2^{519}=1014=-5{\pmod {1019}}}$

実行時間はおよそ です。Pohlig -Hellman アルゴリズムと併用する場合、組み合わせたアルゴリズムの実行時間は です。ここで、 はの最大の素因数です。 ${\displaystyle {\mathcal {O}}({\sqrt {n}})}$${\displaystyle {\mathcal {O}}({\sqrt {p}})}$${\displaystyle p}$${\displaystyle n}$

• Pollard, JM (1978). 「指数計算のためのモンテカルロ法 (mod p )」.計算数学. 32 (143): 918–924. doi :10.2307/2006496. JSTOR  2006496.
• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (2001). 「第 3 章」(PDF) .応用暗号ハンドブック.