Loading AI tools
ウィキペディアから
ポラード・ロー離散対数アルゴリズム (ポラード・ローりさんたいすうアルゴリズム、英語: Pollard's rho algorithm for logarithms)はジョン・ポラード(英語: John Pollard)が1978年に導入した離散対数問題のアルゴリズムであり、ポラード・ロー素因数分解法と似た構造を持つ。
このアルゴリズムの目的は、αが生成する巡回群Gとその元βに対し、となるγを求めることにある。そのためにまず、このアルゴリズムは となるa, b, A, Bを求める。巡回群の位数nが既知の場合、γは方程式の解として求まる。
a, b, A, Bを求めるにはフロイドの循環検出法を用いて、数列のサイクルを検出する。この数列は、関数を用いて計算できるように選ぶ。fが十分にランダムなら、この数列は平均ステップでループに入る。このような関数は、例えば以下のようにすれば定義できる:まず、Gを大きさがほぼ等しい3つの集合, , の非交和に分割する。のときはaとbをそれぞれ2倍する。のときはaをインクリメントする。のときはbをインクリメントする。
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
実行時間はおよそである。ポーリヒ・ヘルマンのアルゴリズム(英語: Pohlig-Hellman algorithm)と組み合わせた場合の実行時間は、pをnの最大の素因数としたときである。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.