13 - 一般名無し質問者 2022/02/09(水) 23:56:15 ID:w+P05Quf0
計算論的安全性の話が入れられなかったから延長戦です
前回の話だとP=NPであるほうが人類にとっては得であるように感じられますが、実はP≠NPでもそれほど嫌な思いはしません。
現代で広く用いられる公開鍵暗号であるRSAは、その安全性が「素因数分解が高速に解けないこと」に依拠しています。
この素因数分解が高速に解けないというのは、計算量理論の言葉で言い直すと「素因数分解がNP問題である」となり、P≠NPでないとむしろ困るということになってしまうのです。
このような暗号解読が計算量理論の問題として難しいことによる暗号の安全性を計算量的安全性と言います。
最後に計算量とアルゴリズムの話題を一般向けにわかりやすく説明した動画を紹介して、一連の計算量理論の講義（？）を終わります
https://www.youtube.com/watch?v=Q4gTV4r0zRs