0:00:00.056,0:00:08.201
2 千年以上前、ユークリッドは、あらゆる数が唯一の方法で[br]因数分解できることを示し、これは秘密鍵に利用できます。

0:00:08.201,0:00:13.833
素因数分解は、非常に難しい問題だと分かります。

0:00:13.956,0:00:21.269
簡単や困難の意味を、「時間複雑性」と呼ばれる概念を[br]導入して説明します。

0:00:21.269,0:00:26.638
我々は全員、掛算の経験がありますが、[br]それは計算をすばやく行うためです。

0:00:26.945,0:00:32.536
掛算用にプログラムすれば、コンピュータは[br]人類よりもはるかに素早く計算できます。

0:00:32.966,0:00:38.294
これは、コンピュータが 2 つの数を掛算するために[br]必要な時間のグラフです。

0:00:38.570,0:00:44.162
もちろん、数が大きくなるにつれて、答を出すために[br]必要な時間も長くなります。

0:00:44.162,0:00:50.127
しかし、計算時間は、かなり大きな数でも、[br]1 秒よりかなり短いものです。

0:00:50.127,0:00:55.613
このため、実行は容易です。[br]これを素因数分解と比較しましょう。

0:00:55.613,0:01:02.540
誰かに 589 の素因数分解を指示されたら、[br]この問題がずっと難しいことが分かります。

0:01:02.540,0:01:10.244
どのような戦術を取るにせよ、589 を割り切れる数を[br]見つけるまで試行錯誤が必要です。

0:01:10.244,0:01:16.292
かなり苦労して 19×31 という[br]素因数分解の答が得られます。

0:01:16.292,0:01:25.668
437,231 を素因数分解するように指示されたら、[br]手計算は諦めてコンピュータを使うでしょう。

0:01:25.944,0:01:34.078
これは小さな数では有効な方法ですが、さらに[br]大きな数では、暴走効果が発生します。

0:01:34.078,0:01:40.744
多数の手順が必要となり、計算に必要な時間が[br]急速に増加するのです。

0:01:40.744,0:01:44.243
数が大きくなると、計算に数十分、[br]さらには数時間かかります。

0:01:44.243,0:01:49.410
さらに巨大な数を因数分解するには[br]数百年、数千年かかるようになります。

0:01:49.410,0:01:57.202
このため、必要時間の増大のために、[br]素因数分解は難しい問題なのです。

0:01:57.202,0:02:01.660
このため、コックスは因数分解を使ってトラップドアを作ったのです。

0:02:01.660,0:02:09.327
ステップ 1: アリスが 150 桁以上の素数乱数を[br]用意します。これを P1 とします。

0:02:09.327,0:02:14.992
また同程度の桁数の第 2 の素数乱数も用意します。[br]これを P2 とします。

0:02:14.992,0:02:23.222
アリスはこれらの 2 つの素数を掛算して、合成数 N を[br]作ります。N は300桁以上の数になります。

0:02:23.222,0:02:28.785
この掛算には 1 秒もかかりません。[br]Web ブラウザでもできます。

0:02:29.877,0:02:35.461
そして、アリスは N の因数分解の解である [br]P1×P2 を隠します。

0:02:35.461,0:02:41.955
アリスが N を他人に渡しても、素因数を見つけるには、[br]コンピュータを使っても何年もかかります。

0:02:42.831,0:02:50.162
ステップ 2: コックスは、N の因数を知っている人だけが使える関数を見つける必要がありました。

0:02:50.162,0:02:54.162
このため、スイスの数学者 オイラーが [br]1760 年に産みだした業績を活用しました。