[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:01.00,0:00:05.00,Default,,0000,0000,0000,,「ある方向では簡単で、逆方向では難しい」
Dialogue: 0,0:00:05.00,0:00:07.00,Default,,0000,0000,0000,,そんな計算手順を考えましょう。
Dialogue: 0,0:00:07.00,0:00:12.00,Default,,0000,0000,0000,,ここで登場するのが、「合同算術」です。これは、「時計演算」とも呼ばれています。
Dialogue: 0,0:00:12.00,0:00:20.00,Default,,0000,0000,0000,,たとえば、46を12で割った余りを求める場合、46単位の長さのヒモを用意します。
Dialogue: 0,0:00:20.00,0:00:24.00,Default,,0000,0000,0000,,そして、そのヒモを周の長さが12単位の「法」と呼ばれる時計に巻き付けます。
Dialogue: 0,0:00:24.00,0:00:28.00,Default,,0000,0000,0000,,そして、ロープの端が来たところが解になります。
Dialogue: 0,0:00:28.00,0:00:32.00,Default,,0000,0000,0000,,ここでは 46 を 12 で割った余り、つまり剰余は 10 になります。
Dialogue: 0,0:00:32.00,0:00:39.00,Default,,0000,0000,0000,,簡単ですね。これを機能させるために、まず17などの素数の「法」を扱います。
Dialogue: 0,0:00:39.00,0:00:44.00,Default,,0000,0000,0000,,17の「原始根」を設定します。今回は３で考えます。
Dialogue: 0,0:00:44.00,0:00:48.00,Default,,0000,0000,0000,,３には重要な性質があります。さまざまな指数で累乗したときに、
Dialogue: 0,0:00:48.00,0:00:52.00,Default,,0000,0000,0000,,解が時計の周囲に均等に分散されるのです。
Dialogue: 0,0:00:52.00,0:01:00.00,Default,,0000,0000,0000,,３は「生成元」と呼ばれています。３を任意の指数 x で累乗した場合、
Dialogue: 0,0:01:00.00,0:01:05.00,Default,,0000,0000,0000,,解は、等しい頻度で、偏りなく、0と17の間の任意の整数になります。
Dialogue: 0,0:01:05.00,0:01:08.00,Default,,0000,0000,0000,,しかし、逆向きの演算は困難です。
Dialogue: 0,0:01:08.00,0:01:14.00,Default,,0000,0000,0000,,たとえば、3を何乗して17で割った余りが12になるか簡単に分かるでしょうか。
Dialogue: 0,0:01:14.00,0:01:17.00,Default,,0000,0000,0000,,これは「離散対数」の問題と呼ばれます。
Dialogue: 0,0:01:17.00,0:01:20.00,Default,,0000,0000,0000,,ここまで、一方向の関数について考えました。
Dialogue: 0,0:01:20.00,0:01:23.00,Default,,0000,0000,0000,,これは簡単に実行できますが、逆方向は難しい関数です。
Dialogue: 0,0:01:23.00,0:01:30.00,Default,,0000,0000,0000,,12という数字が与えられても、それを生み出した指数を見つけるには、大変な試行錯誤が必要です。
Dialogue: 0,0:01:30.00,0:01:32.00,Default,,0000,0000,0000,,どれぐらい大変でしょうか。
Dialogue: 0,0:01:32.00,0:01:39.00,Default,,0000,0000,0000,,小さな数字なら簡単です。けれど、何百桁にもなる素数の「法」を使用した場合、
Dialogue: 0,0:01:39.00,0:01:42.00,Default,,0000,0000,0000,,実際には解くことができなくなります。
Dialogue: 0,0:01:42.00,0:01:47.00,Default,,0000,0000,0000,,地球上のすべてのコンピュータを使っても、全ての可能性のある数を見つけ出すには、
Dialogue: 0,0:01:47.00,0:01:49.00,Default,,0000,0000,0000,,何千年もかかってしまうでしょう。
Dialogue: 0,0:01:49.00,0:01:53.00,Default,,0000,0000,0000,,つまり、一方向関数の強みは、逆方向に計算するのに膨大な時間がかかるという点なのです。