ポラードのカンガルーアルゴリズム

計算数論および計算代数 において、ポラードのカンガルーアルゴリズム（ポラードのラムダアルゴリズムとも呼ばれる。下記の命名を参照）は、離散対数問題を解くためのアルゴリズムである。このアルゴリズムは、1978 年に数論学者のジョン・M・ポラードによって、同じ問題を解くためのより有名なポラードのローアルゴリズムと同じ論文で発表された。 ^{[ 1 ] [ 2 ]}ポラードは、素数pを法とする乗法群の離散対数問題へのアルゴリズムの適用について説明したが、実際には一般的な離散対数アルゴリズムであり、任意の有限巡回群で機能する。

仮定する${\displaystyle G}$位数が の有限巡回群である${\displaystyle n}$これは要素によって生成されます${\displaystyle \alpha }$、そして我々は離散対数を見つけようとする${\displaystyle x}$要素の${\displaystyle \beta }$基地へ${\displaystyle \alpha }$言い換えれば、人は${\displaystyle x\in Z_{n}}$そのため${\displaystyle \alpha ^{x}=\beta }$ラムダアルゴリズムを使用すると、${\displaystyle x}$ある期間内に${\displaystyle [a,\ldots ,b]\subset Z_{n}}$と設定することで、可能な対数の全範囲を探索できます。${\displaystyle a=0}$そして${\displaystyle b=n-1}$。

1. セットを選択してください${\displaystyle S}$平均の正の整数のおよそ${\displaystyle {\sqrt {ba}}}$そして擬似乱数マップを定義する${\displaystyle f:G\rightarrow S}$。

2. 整数を選択してください${\displaystyle N}$そして、群の要素のシーケンスを計算する${\displaystyle \{x_{0},x_{1},\ldots ,x_{N}\}}$によると：

• ${\displaystyle x_{0}=\alpha ^{b}\,}$
• $${\displaystyle x_{i+1}=x_{i}\alpha ^{f(x_{i})}{\text{ for }}i=0,1,\ldots ,N-1}$$

3. 計算する

${\displaystyle d=\sum _{i=0}^{N-1}f(x_{i}).}$

以下の点に注目してください。

${\displaystyle x_{N}=x_{0}\alpha ^{d}=\alpha ^{b+d}\,.}$

4. 2番目のグループ要素のシーケンスの計算を開始します${\displaystyle \{y_{0},y_{1},\ldots \}}$によると：

• ${\displaystyle y_{0}=\beta \,}$
• ${\displaystyle y_{i+1}=y_{i}\alpha ^{f(y_{i})}{\text{ for }}i=0,1,\ldots ,N-1}$

そして対応する整数列${\displaystyle \{d_{0},d_{1},\ldots \}}$によると：

${\displaystyle d_{n}=\sum _{i=0}^{n-1}f(y_{i})}$。

以下の点に注目してください。

${\displaystyle y_{i}=y_{0}\alpha ^{d_{i}}=\beta \alpha ^{d_{i}}{\mbox{ for }}i=0,1,\ldots ,N-1}$

5. 計算を停止する${\displaystyle \{y_{i}\}}$そして${\displaystyle \{d_{i}\}}$以下のいずれかの条件が満たされた場合：

A)${\displaystyle y_{j}=x_{N}}$一部の人にとって${\displaystyle j}$シーケンスが${\displaystyle \{x_{i}\}}$そして${\displaystyle \{y_{j}\}}$このように「衝突」すると、次のようになります。

${\displaystyle x_{N}=y_{j}\Rightarrow \alpha ^{b+d}=\beta \alpha ^{d_{j}}\Rightarrow \beta =\alpha ^{b+d-d_{j}}\Rightarrow x\equiv b+d-d_{j}{\pmod {n}}}$

これで終わりです。

B)${\displaystyle d_{i}>b-a+d}$. もしこれが発生した場合、アルゴリズムは検出に失敗しました。${\displaystyle x}$. 選択を変更することで、次の試みを行うことができます。${\displaystyle S}$および/または${\displaystyle f}$。

ポラードはアルゴリズムの時間計算量を次のように表している。${\displaystyle O({\sqrt {b-a}})}$確率論的議論に基づいて、${\displaystyle f}$擬似ランダムに動作します。${\displaystyle a,b}$表現方法${\displaystyle O(\log b)}$ビット、これは問題のサイズに対して指数関数的です（ただし、時間のかかる単純な総当たりアルゴリズムに比べれば依然として大幅な改善です）。${\displaystyle O(b-a)}$)指数関数以下の時間で実行される離散対数アルゴリズムの例については、指数計算アルゴリズムを参照してください。

このアルゴリズムは2つの名前でよく知られている。

1つ目は「ポラードのカンガルーアルゴリズム」です。この名前は、アルゴリズムを紹介する論文で使用されているアナロジーに由来しており、その論文では、飼い慣らされたカンガルーを使って野生のカンガルーを捕獲するという例えでアルゴリズムが説明されています。ポラードは^{[ 3 ]} 、このアナロジーは、 RSA公開鍵暗号システムの解説として同じ号のサイエンティフィック・アメリカンに掲載された「興味深い」記事に触発されたものだと説明しています。その記事^{[ 4 ]}では、カンガルーをトレッドミルに乗せて、さまざまな速度での酸素消費量で測定したカンガルーの移動のエネルギーコストを測定した実験について説明しています。

2つ目は「ポラードのラムダアルゴリズム」です。ポラードの別の離散対数アルゴリズムであるポラードのローアルゴリズムの名前と同様に、この名前はアルゴリズムの視覚化とギリシャ文字ラムダ(${\displaystyle \lambda }$) 文字ラムダの短いストロークは、次のシーケンスに対応します。${\displaystyle \{x_{i}\}}$なぜなら、x の右側の位置 b から始まるからです。したがって、長いストロークは次のシーケンスに対応します。${\displaystyle \{y_{i}\}}$これは最初のシーケンスと「衝突」し（ラムダのストロークが交差するのと同じように）、その後それに続きます。

ポラードは「カンガルーアルゴリズム」という名称を好むと表明している^{[ 5 ]。}これは、彼のローアルゴリズムのいくつかの並行バージョン（これも「ラムダアルゴリズム」と呼ばれている）との混同を避けるためである。

• ディンキンのカードマジック
• クラスカルカウント^{[ 6 ]}
• レインボーテーブル

• Montenegro, Ravi [at Wikidata] ; Tetali, Prasad V. (2010-11-07) [2009-05-31].野生のカンガルーを捕まえるのにどれくらい時間がかかりますか? (PDF) . 第41回 ACM 理論計算機科学シンポジウム (STOC 2009) 議事録。pp. 553–560 . arXiv : 0812.0789 . doi : 10.1145/1536414.1536490 . S2CID 12797847 . 2023-08-20のオリジナルからアーカイブ(PDF) 。2023-08-20 に取得。