私はコンピュータサイエンスの初心者です。実行時間について何かを学びましたが、理解したことが正しいかどうかわかりません。だから私を助けてください。
したがって、素因数分解は現在、多項式時間の問題ではありませんが、素数性テストは問題です。チェックする番号がnであると仮定します。1からsqrt（n）までのすべての数値がnを除算できるかどうかを判断するためだけにプログラムを実行し、答えが「はい」の場合は、その数値を格納します。このプログラムは多項式時間だと思いますね。
私が間違っている可能性のある方法の1つは、因数分解プログラムが最初に検出された素数ではなく、すべての素数を検出する必要があることです。だから多分これが理由です。
ただし、公開鍵暗号では、暗号を攻撃するには、多数の素因数を見つけることが不可欠です。通常、多数（公開鍵）は2つの素数の積にすぎないため、一方の素数を見つけることは、もう一方の素数を見つけることを意味します。これは多項式時間である必要があります。では、なぜ攻撃が困難または不可能なのですか？
「多項式因数分解アルゴリズム」のような複雑さのカジュアルな説明は、一般に、入力の解釈ではなく、入力のサイズに関する複雑さを指します。したがって、人々が「既知の多項式因数分解アルゴリズムがない」と言うとき、それらは、Nに関して時間多項式で実行されるNビットの自然数を因数分解するための既知のアルゴリズムがないことを意味します。数自体に関しては多項式ではなく、最大2^ Nになる可能性があります。
因数分解の難しさは、理解しやすく、人間の知識の端にすぐに連れて行ってくれる美しい数学の問題の1つです。この主題に関する（今日の）知識を要約すると、なぜそれが難しいのか、ある程度の証拠がなく、多項式時間よりも長く（ただし、指数時間よりも大幅に短い）実行した最良の方法がわかりません。素数性テストがPでも行われているという結果は、かなり最近のものです。リンクされたウィキペディアのページを参照してください。
難しさについて私が知っている最も良いヒューリスティックな説明は、素数がランダムに分布しているということです。理解しやすい結果の1つは、ディリクレの定理です。この定理は、すべての等差数列には無限に多くの素数が含まれていると言います。言い換えると、素数は進行に関して密であると考えることができます。つまり、それらに遭遇することを避けられません。これは、そのような結果のかなり大きなコレクションの中で最も単純です。それらすべてにおいて、素数は乱数と非常によく似た方法で表示されます。
したがって、ファクタリングの難しさは、ワンタイムパッドを逆にすることが不可能であることに類似しています。ワンタイムパッドでは、XORがわからないものと、わからないものがあります。XORの結果を知っている個々のビットに関するゼロ情報を取得します。「ビット」を「プライム」に置き換え、乗算をXORに置き換えると、因数分解の問題が発生します。これは、2つの乱数を掛け合わせたようなものであり、製品から得られる情報はほとんどありません（ゼロの情報ではありません）。
1からsqrt（n）までのすべての数値がnを除算できるかどうかを判断するためだけにプログラムを実行し、答えが「はい」の場合は、その数値を格納します。
除算性テストは数値が大きいほど時間がかかることを無視しても、このアプローチでは、に1桁の（2進数）を追加するだけでほぼ2倍の時間がかかりますn。（実際には、2桁を追加すると2倍の時間がかかります）
これが指数ランタイムの定義だと思いますn。1ビット長くすると、アルゴリズムに2倍の時間がかかります。
ただし、この観察結果は、提案したアルゴリズムにのみ適用されることに注意してください。素因数分解が多項式であるかどうかはまだ不明です。暗号学者は確かにそうではないことを望んでいますが、万が一の場合に備えて、素因数分解が難しいことに依存しない代替アルゴリズム（楕円曲線暗号など）もあります...