P != NP（P≠NP）予想が証明されるかも

>>112
＞P≠NPが証明されたらサマウォに出てきたようなRSA暗号は安全であることを証明できるんだけど

できない．

クラスNPに属する問題の中で一番難しい問題は
「その問題を1個解けば、クラスNPに属する他の問題もみんな解けてしまう」
という性質を持つ「NP完全問題」と呼ばれる特別な問題群．

もしもNP完全問題のうち，どれか1個でもクラスPに属することを証明できれば
その時点で，クラスNPの全ての問題がクラスPに属することになる．
つまりP=NPを証明したことになる．

だから，今回のP≠NPの証明が正しければ，その時点で
「NP完全問題は，どれ一つとっても絶対にクラスPに含まれない」ということまで言える．

一方，RSA暗号の安全性は「素因数分解問題が難しい」という仮定を根拠にしている
（厳密に言うと，もうちょっと易しい問題の困難さを根拠にしている）
この素因数分解問題は，確かにクラスNPには分類されるものの
おそらくNP完全問題にはならないだろうと予想されている
（つまりNPの中ではそれほど難しくない問題だろうと予想されている）
なので，P≠NPが証明されたとしても，素因数分解問題がクラスPに含まれないかどうかはまだ不明．
つまりRSA暗号が本当に安全かどうかもまだ不明．