1971年、アメリカの数学者ダニエル・シャンクスは、デジタルマネーとは全く関係のない問題に対する方法を発表しました。そのアイデアは、1つの段落に収まるほどシンプルで、半世紀を経てもなお有効です。つまり、端から端まで全ての道を辿るのではなく、両端から半分ずつ進んで中間で出会うというものです。
ここでの問題は、前のレッスンで扱った問題の好意的なバージョンです。公開鍵Qが知られており、それがk倍のGであることがわかっていて、kが0からNの間にあることもわかっています。力ずくでkを見つけるにはNステップが必要ですが、シャンクスの方法では約2倍の√Nステップで済みます。
このトリックは、kを異なる方法で表現することです。Nの平方根を上に丸めたものをmと呼びます。0からNの間のすべての数は、i×m+jとして表現できます。ここで、iとjはm未満です。これは、47を4つの十と7つの単位として表現するのと同じ分解で、10の代わりにmを使用します。
この方程式に代入すると、Qはi×m+jすべてをGで掛けたものになります。jを左側に移動させると、Q-j×Gはi×mGのポイントになります。ここで何が起こったかに注目してください。左側にはjに依存するものだけがあり、右側にはiに依存するものだけがあります。両側が分離されました。
ここから名前が来ています。ベビーステップは左側のm個の値です。各jに対してQ-j×Gを計算し、各結果をテーブルに保存します。ジャイアントステップは右側のm個の値です。各iに対してi×mGのポイントを計算し、各結果をテーブルで探します。値が一致すると、対応するiとjがkを明らかにします。なぜなら、kはi×m+jだからです。
ビットで見ると、節約は明確です。70ビットの範囲には2^69の候補があり、その平方根は約2^34.5です。これは、各側で240億ステップ以上になります。数十億の操作を毎秒行うマシンは、これを数分で処理します。何千年もかかるわけではありません。
しかし、上記の計算は時間のものであり、方法は別の通貨で請求されます。ベビーステップのテーブルは、ジャイアントステップが始まる前に完全に存在する必要があります。これは240億のエントリであり、各エントリは少なくともポイントの座標の一部とjの値を保存します。これには、行ごとに約30バイトが必要です。70ビットの範囲では、約750ギガバイトのメモリが必要です。
メモリは時間と同じ平方根で増加します。80ビットでは約24テラバイト、90ビットではほぼ800テラバイトが必要です。これをメモリではなくディスクに保存しても解決しません。なぜなら、各ジャイアントステップが予測不可能なアドレスにアクセスするため、ディスクはランダムアクセスを好まないからです。この方法は計算によって制限されるのではなく、検索時間によって制限されます。
保存するポイントの一部だけを保持し、偽陽性を後で確認することでテーブルを縮小するバージョンも存在します。これらは定数の要因で助けになりますが、問題の性質を変えることはありません。ベビーステップとジャイアントステップは、メモリを時間に交換する方法であり、この交換にはすぐに到達する物理的な限界があります。
この限界から逃れるために、別の方法が探されました。それは、時間において同じ平方根を要し、メモリはほとんど必要としない方法です。それは存在し、動物の名前を持ち、これまでに解決された最大の課題を打ち破ったアルゴリズムです。次のレッスンでは、ポラードのカンガルーについて学びます。