私は最近、暗号化における素因数の一般的な使用について読んでいます。私が読んだところはどこでも、キーの素因数を見つけるために（指数時間ではなく）多項式時間で動作する「PUBLISHED」アルゴリズムはないと述べています。
多項式時間で動作するアルゴリズムが発見または公開された場合、理論やコンピューター サイエンスの世界とは対照的に、現実世界のコンピューティング環境にどのような影響を与えるでしょうか。私たちが暗号にどれだけ依存しているかを考えると、暗号は突然停止するでしょう。
これを念頭に置いて、P = NP が真である場合、何が起こるか、それがまだ証明されていないという事実にどれだけ依存するか.
私は初心者なので、質問の間違いをお許しください。
これを念頭に置いて、N = NP が真である場合、彼らは教えてくれるでしょうか。
「彼ら」とは誰ですか? それが本当なら、私たちは知っているでしょう。コンピューター科学者？それは私達だ。暗号学者と数学者？専門家？専門家？私たちのような人。インターネットのユーザー、さらにはスタック オーバーフローのユーザー。
言われる必要はありません。わかります。
科学と研究は密室で行われるわけではありません。誰かが P = NP であることがわかった場合、これを秘密にしておくことはできません。これは、単に研究が公開される方法のためです。原則として、誰もがそのような研究にアクセスできます。
発見者次第です。
コンラッドの主張に反して、国の後援の下で暗号化を研究している NSA やその他の組織は、秘密裏に研究と科学を行っています。そして、彼らはいくつかの重要な発見について、出版された学術研究者を「スクープ」しました。最後に、彼らは学術研究者によって独自に発見された後、何年にもわたって暗号解読の進歩を差し控えてきた歴史があります.
私は陰謀論にはあまり興味がありません。しかし、政府が因数分解の問題に多くの「闇」のお金を使っていないとしたら、私は非常に驚かれることでしょう。そして、何らかの結果が得られた場合、それらは秘密にされます。テロを回避するために相互に調整を怠ったとして、米国の機関には多くの批判が向けられています。NSA が収集した情報を FBI に通知することは、NSA の能力について「多くのこと」を明らかにすることになるかもしれません。
このインタビューで Bruce Schneier に投げかけられた最初の質問が興味深いと思うかもしれません。結論として、NSA は常に学界より優位に立っていますが、そのマージンは縮小しています。
その価値のために、NSA は RSA 暗号化ではなく、楕円曲線 Diffie-Hellman 鍵協定の使用を推奨しています。彼らは小さいキーが好きですか？彼らは量子コンピューティングを先取りしていますか? または … ？
因数分解が NP 完全であるとは知られていない (そしてそうではないと推測されている) ことに注意してください。したがって、因数分解の P アルゴリズムを実証しても、P=NP は意味されません。代わりに、暗号化アルゴリズムの基盤を何らかの NP 完全問題に切り替えることができると思われます。
P = NPACM からの 記事は次のとおりです。http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext
リンクから：
多くの人は、P = NP の場合、公開鍵暗号化が不可能になるというマイナス面に焦点を当てています。確かに、しかし P = NP から得られるものは、インターネット全体を歴史の脚注のように見せるでしょう。
すべての NP 完全最適化問題が簡単になるため、すべてがはるかに効率的になります。あらゆる形態の輸送が最適にスケジュールされ、人や物資をより迅速かつ安価に移動できます。製造業者は生産を改善して速度を上げ、無駄を減らすことができます。そして、私は表面をなぞっているだけです。
この引用を考えると、私は彼らが世界に伝えると確信しています.
GPU (または GPU のクラスター) で多数の素因数分解を行っていたカナダ (?) の研究者がいたと思います。それらが多項式時間で因数分解されたという意味ではありませんが、チップアーキテクチャは因数分解に有利でした。
合成数を素因数分解する真に効率的なアルゴリズムが発見された場合、最も大きな直接的な影響は電子商取引に及ぶと思います。具体的には、因数分解が一方向関数であることに依存しない形式の暗号化が開発されるまで、それは停止します。
過去 40 年間、民間部門で暗号化に関する多くの研究が行われてきました。これは、仮想通貨が主に軍や秘密の政府機関の権限にあった前の時代からの大きな転換でした。これらの秘密機関は間違いなくこの変化に抵抗しようとしましたが、知識が発見されると、それを秘密にしておくことは非常に困難です. それを念頭に置いて、P = NP 問題の解決策は、この 1 つの領域に影響を与える可能性があるにもかかわらず、長い間秘密のままになるとは思いません。潜在的な利点は、はるかに広い範囲のアプリケーションにあります。
ちなみに、量子暗号についてはいくつかの研究が行われており、
特定の数学関数の計算の難しさに依存する従来の公開鍵暗号とは対照的に、量子力学の基礎に依存しており、盗聴の兆候や鍵の安全性の保証を提供することはできません。
この技術を使用した最初の実用的なネットワークは、2008 年にオンラインになりました。
ちなみに、量子コンピューティングの領域に入ると、多項式時間を考慮することができます。 ショアのアルゴリズムとしても知られる、量子コンピューティングに関するロブ・パイクの講演の 25 ページのメモを参照してください。