矢吹健太朗のBLACK CAT★ 黒猫No.251

>>435
RSAという暗号の造り方。
素数a、bを用意する。a*bの値cだけはヒントとして出す。
さらに（a-1）*（b-1）と公約数を持たない数dを１つだけヒントに出す。
最後にd*eが（a-1）*（b-1）の倍数＋１になるようなをeを用意する。eは明かさない。
好きな数字を考える。それをd乗したものをa*bで割った余りを暗号とすればよい。

暗号を解くにはその数字をe乗してa*bで割った余りを求めるだけでよい。
が、わかっている数字はa*bとdである。eは明かされていない。
eを求めるにはaとbの値が必要である。
aとbを求めるにはa*bを素因数分解しなければならない。これが時間がかかる。
作成者は何万桁もの素数を２つかけるだけで用足りるが
解読者は何億桁もの数字から素数の組み合わせを考えなければならない。
この組み合わせは膨大で探し出すのはコンピュータを使っても困難だ。
しかも作成者は素数の桁をいくらでも跳ね上げることができる。これが素数暗号。
将来的に量子コンピュータを利用して求めようとする動きがあるが
開発されない限り完璧なセキュリティなのだ。詳しいことはしらんけど。