素因数分解とRSA暗号の関係

唐突に「極黒のブリュンヒルデ」が読みたくなり、 漫画を買って読んでいた。 早速読み始めると、 カズミが登場する場面で次のような話が出てきた。 「まさかお前、素因数分解が出来るのか？」 「ネットには当然セキュリティがある、その暗号の鍵に使われているのは巨大な素数なんだ」 「素因数分解をするには膨大な時間がかかるという前提があって成り立つセキュリティだ」 大学でここらへんを学んだ記憶は無いし、 気になったので調べてみる。 （調べてたら、サマーウォーズもRSA暗号を使った話だったらしい） RSA暗号 まず、Wikipediaを見てみる。 RSA暗号（RSAあんごう）とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 暗号とデジタル署名を実現できる方式として最初に公開されたものである。 確かに、素因数分解の仕組みを利用したものらしい。 RSA暗号方