トップQs
タイムライン
チャット
視点

ポラード・ロー離散対数アルゴリズム

ウィキペディアから

Remove ads
Remove ads

ポラード・ロー離散対数アルゴリズム (ポラード・ローりさんたいすうアルゴリズム、英語: Pollard's rho algorithm for logarithms)はジョン・ポラード英語: John Pollard1978年に導入した離散対数問題のアルゴリズムであり、ポラード・ロー素因数分解法と似た構造を持つ。

このアルゴリズムの目的は、αが生成する巡回群Gとその元βに対し、となるγを求めることにある。そのためにまず、このアルゴリズムは となるa, b, A, Bを求める。巡回群の位数nが既知の場合、γは方程式の解として求まる。

a, b, A, Bを求めるにはフロイドの循環検出法を用いて、数列のサイクルを検出する。この数列は、関数を用いて計算できるように選ぶ。fが十分にランダムなら、この数列は平均ステップでループに入る。このような関数は、例えば以下のようにすれば定義できる:まず、Gを大きさがほぼ等しい3つの集合, , の非交和に分割する。のときはabをそれぞれ2倍する。のときはaをインクリメントする。のときはbをインクリメントする。

Remove ads

アルゴリズム

要約
視点

Gを位数p巡回群αGの生成元とし、Gの分割とする。写像を以下のように定める:

また、

と定める。

 入力 a: Gの生成元, b: Gの元
 出力 ax = bを満たす整数xを返すか、失敗する

 Initialise a0  0, b0  0, x0  1  G, 

 i  1
 loop
     xi  f(xi-1), 
     ai  g(xi-1, ai-1), 
     bi  h(xi-1, bi-1)

     x2i  f(f(x2i-2)), 
     a2i  g(f(x2i-2), g(x2i-2, a2i-2)), 
     b2i  h(f(x2i-2), h(x2i-2, b2i-2))

     if xi = x2i then
         r  bi - b2i
         if r = 0 return failure
         x  r−1(a2i - ai) mod p
         return x
     else # xi  x2i
         i  i+1, 
         break loop
     end if
  end loop
Remove ads

計算量

実行時間はおよそである。ポーリヒ・ヘルマンのアルゴリズム英語: Pohlig-Hellman algorithmと組み合わせた場合の実行時間は、pnの最大の素因数としたときである。

Remove ads

参考文献

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads