小さな一歩、大きな一歩

数学の一分野である群論において、ベイビーステップ・ジャイアントステップは、ダニエル・シャンクスによる有限アーベル群の元の離散対数または順序を計算するための中間の アルゴリズムである。^{[1]離散対数問題は、}公開鍵暗号の分野にとって根本的に重要である。

最も一般的に使用されている暗号化システムの多くは、離散対数の計算が非常に難しいという仮定に基づいています。離散対数の計算が困難であればあるほど、データ転送のセキュリティが強化されます。離散対数問題の難易度を上げる 1 つの方法は、暗号システムをより大きなグループに基づいて構築することです。

このアルゴリズムは、空間と時間のトレードオフに基づいています。これは、離散対数を求める単純な方法である試行乗算をかなり単純に修正したものです。

位数 の巡回群 、群の生成元、群の元が与えられたとき、次のような 整数を求める問題である。${\displaystyle G}$${\displaystyle n}$ ${\displaystyle \alpha}$${\displaystyle \beta}$${\displaystyle x}$

${\displaystyle \alpha^{x}=\beta \,.}$

ベイビーステップジャイアントステップアルゴリズムは、次の書き換えに基づいています。 ${\displaystyle x}$

${\displaystyle x=im+j}$

${\displaystyle m=\left\lceil {\sqrt {n}}\right\rceil }$

${\displaystyle 0\leq i<m}$

${\displaystyle 0\leq j<m}$

したがって、次のようになります。

${\displaystyle \alpha ^{x}=\beta \,}$

${\displaystyle \alpha ^{im+j}=\beta \,}$

${\displaystyle \alpha ^{j}=\beta \left(\alpha ^{-m}\right)^{i}\,}$

アルゴリズムはのいくつかの値を事前計算します。次に を固定し、試行乗算の方法で、上記の合同式の右側の の値を試します。事前計算された の値を使用して、 の任意の値に対して合同式が満たされるかどうかをテストします。 ${\displaystyle \alpha^{j}}$${\displaystyle j}$${\displaystyle m}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \alpha^{j}}$

入力:生成元αと元β を持つ、位数nの巡回群G。

出力: を満たす値x。 ${\displaystyle \alpha^{x}=\beta}$

1. m ← 天井( √n )
2. 0 ≤ j < mであるすべてのjについて:
   1. α ^{j を}計算し、ペア ( j , α ^j ) をテーブルに格納します。(§ 実践を参照)
3. α ^{− m}を計算します。
4. γ ← β（γ = βと設定）
5. 0 ≤ i < mであるすべてのiについて:
   1. γ が表内のいずれかのペアの2 番目の要素 ( α ^{j ) であるかどうかを確認します。}
   2. そうであれば、im + jを返します。
   3. そうでない場合は、γ ← γ • α ^{− m}です。

ベイビーステップ ジャイアントステップ アルゴリズムを高速化する最善の方法は、効率的なテーブル検索方式を使用することです。この場合、最適なのはハッシュ テーブルです。ハッシュは 2 番目のコンポーネントに対して実行され、メイン ループのステップ 1 でチェックを実行するために、γ がハッシュされ、結果のメモリ アドレスがチェックされます。ハッシュ テーブルは時間内に (一定時間で) 要素を取得して追加できるため、これによってベイビーステップ ジャイアントステップ アルゴリズム全体の速度が低下することはありません。 ${\displaystyle O(1)}$

アルゴリズムの空間計算量は ですが、アルゴリズムの時間計算量は です。この実行時間は、単純なブルート フォース計算の実行時間よりも短くなっています。 ${\displaystyle O({\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O(n)}$

ベイビーステップジャイアントステップアルゴリズムは、係数が大きすぎない素数である場合、盗聴者がディフィーヘルマン鍵交換で生成された秘密鍵を導出するために使用できます。係数が素数でない場合は、ポーリッヒ・ヘルマンアルゴリズムのアルゴリズムの複雑さは小さく、同じ問題を解決できる可能性があります。^[2]

• ベイビーステップ ジャイアントステップ アルゴリズムは汎用アルゴリズムです。これはすべての有限巡回群に対して機能します。
• グループGの正確な順序を事前に知る必要はありません。n が単にグループ順序の上限であっても、アルゴリズムは機能します。
• 通常、ベイビーステップ ジャイアントステップ アルゴリズムは、位数が素数のグループに使用されます。グループの位数が合成数の場合、Pohlig-Hellman アルゴリズムの方が効率的です。
• このアルゴリズムにはO ( m ) のメモリが必要です。アルゴリズムの最初のステップでより小さなm を選択すると、メモリの使用量を減らすことができます。これを行うと実行時間が長くなり、 O ( n / m ) になります。代わりに、対数にポラードのローアルゴリズムを使用することもできます。このアルゴリズムは、ベイビーステップジャイアントステップアルゴリズムとほぼ同じ実行時間で、メモリ要件がわずかです。
• このアルゴリズムは、1971年に初めて論文を発表したダニエル・シャンクスの功績とされていますが、1994年に発表されたネチャエフの論文^[3]では、ゲルフォンドが1962年にこのアルゴリズムを知っていたと述べられています。
• ^{元のアルゴリズムの最適化バージョンも存在し、 [4]}の衝突のない切り捨てルックアップテーブルや^{[5]で提案された否定マップとモンゴメリの同時モジュラー反転を使用するものなどがある。}

• H. Cohen、「計算代数的数論コース」、Springer、1996年。
• D. Shanks、「クラス数、因数分解と種数の理論」。Proc. Symp. Pure Math. 20、415〜440 ページ。AMS、プロビデンス、ロードアイランド州、1971 年。
• A. Stein と E. Teske、「最適化されたベイビーステップ-ジャイアントステップ法」、Journal of the Ramanujan Mathematical Society 20 (2005)、第 1 号、1–32 ページ。
• AV Sutherland、「ジェネリック群における順序計算」、博士論文、MIT、2007年。
• DC Terr、Shanks のベイビーステップジャイアントステップアルゴリズムの修正、Mathematics of Computation 69 (2000)、767–773。doi :10.1090/ S0025-5718-99-01141-2

• 小さな一歩から大きな一歩まで - C ソースコードの例