問題タブ [prime-factoring]

暗号化アルゴリズムのセキュリティは、大きな数の素因数分解にどのように依存していますか?

たとえば、いくつかの数学プログラミング フォーラムで、Quadratic Sieve または General Number Field Sieve を使用すると、市販のハードウェアで比較的簡単に 256 ビットの数値を因数分解できると読んだことがあります。

これは、RSA、AES などのアルゴリズムのセキュリティを破ることができるとどのように解釈されますか? 数字をキーの長さだけ因数分解できれば十分ですか?

少し光を当てることができる暗号化と暗号化アルゴリズムに精通している人はいますか?

Python でエラトステネスのふるいを実装しようとしていますが、たとえば779695003923747564589111193840021の平方根までのすべての素数を見つけようとすると、range() の結果に項目が多すぎるというエラーが表示されます。私の質問は、この問題を回避するにはどうすればよいかということです。リストを while ループでインスタンス化すると、(ページファイルの使用を開始する前に) メモリを使いすぎているというエラーが表示されます。2 つを以下に示します。

range() の使用

while の使用:

最大の素因数を見つけるプログラムを PHP で作成しました。読み込みがかなり速いので、かなり最適化されていると思います。ただし、問題があります。非常に大きな数の素因数はカウントされません。プログラムは次のとおりです。

公開鍵暗号について私が読んだ説明では、2 つの非常に大きな素数を掛け合わせることで大きな数が得られると言われています。大きな素数の積を因数分解することは、ほとんど不可能なほど時間がかかるため、安全です。

これは、レインボー テーブルで簡単に解決できる問題のようです。使用される素数のおおよそのサイズが分かっていて、それらが 2 つあることがわかっている場合は、すぐにレインボー テーブルを作成できます。それは非常に大きなテーブルになりますが、それは実行でき、タスクはハードウェア全体で並列化できます。

レインボー テーブルが、大きな素数の乗算に基づいて公開鍵暗号を打ち負かす効果的な方法ではないのはなぜですか?

免責事項: 明らかに、何万人ものクレイジーでスマートなセキュリティ意識の高い人々が、私が午後に考えたことを何十年も見逃していたわけではありません。単純化された素人の説明を読んでいたため（例：2つ以上の数字が使用されている場合）、これを誤解していると思いますが、知識のギャップがどこにあるかを知るにはまだ十分に知りません.

編集: 「レインボー テーブル」がルックアップ テーブルで事前に計算されたハッシュを使用することに関連していることは知っていますが、上記はレインボー テーブル攻撃のように聞こえるため、ここではこの用語を使用しています。

編集 2:回答で述べたように、すべての素数だけを保存する方法はなく、すべての積を保存する方法はありません。

• このサイトによると、512 ビットの素数は、((2^511) * 1) / (512 log(2)) = 4.35 × 10 ¹⁵¹ほど多く存在します。
• 太陽の質量は 2 × 10 ³⁰ kg または 2 × 10 ³³ g
• これは、太陽 1 グラムあたり2.17 × 10 ^{124個の素数です。}
• 数量 キロバイトに収まる 512 ビットの数値: 1 kb = 1024 バイト = 8192 ビット / 512 = 16
• これは 1 テラバイトに収まります: 16*1024*1024*1024 = 1.72 × 10 ¹⁰
• ペタバイト: 16*1024*1024*1024*1024 = 1.72 × 10 ¹³
  
• エクサバイト: 16*1024*1024*1024*1024*1024 = 1.72 × 10 ¹⁶

1 エクサバイトが 1 グラムの重さであったとしても、これらすべての数値を太陽の質量のハード ドライブに収めるのに必要な2.17 × 10 ^{124にはほど遠いです。}

理想的には空のセルがないように、n 個の要素からテーブルを作成する最適な方法を探していますが、同時に、テーブルの次元の列/行の比率ができるだけ 1 に近くなります。

もちろん、n が平方数の場合は簡単です。

n が素数の場合、空のセルがあることも明らかなので、これを処理する現在の方法は次のとおりです。

他のすべてのケースでは、私の計画は、n の素因数を取得し、組み合わせの比率が 1 に最も近いものをすべての可能な順列で検索することです。

私の質問は次のとおりです。これを行うためのより良い方法はありますか? または、少なくとも素因数のすべての可能な組み合わせをテストする必要がない方法はありますか?

元々、このコードを機能させるのに問題がありましたが、少し調整した後、デバッグして準備が整いました。

私はこのプログラムのいくつかの改訂を経験しました。私は整数値から始めましたが、数値が大きすぎてintに収まらないことがわかりました。次に、BigIntegersに変更しました。これは面倒ですが、実行可能であることがわかりました。そこから、（最初から行うべきだったように）longに切り替えて、コードの実行時間を8分の1（またはそれ以上）に短縮しました。

現在のコードは次のとおりです。

と

何時間も実行されていますが、まだ何も見つかりません。このパズルを解く典型的な方法は、560GBのデータを解析するようなものだとオンラインで見ました=/。

これをスピードアップするためのヒントはありますか？

どうもありがとう、

ユスティニアヌス

編集：

最適化されたコード：

と

で実行

合成数を入力として受け入れています。そのすべての因数と、その数の最大の素因数を印刷したいと思います。私は次のコードを書きました。51という数字までは問題なく動作しています。ただし、51より大きい数字を入力すると、間違った出力が表示されます。コードを修正するにはどうすればよいですか？

これは、離散数学の割り当てとして取得します。私はこのようにしようとします。

私自身の演習として、ミラーラビン素検定を実装しています。（SICPを介した作業）。私はフェルマーの小定理を理解し、それをうまく実行することができました。ミラーラビン素検定で私がつまずくのは、この「1modn」ビジネスです。1 mod n（nはランダムな整数）は常に1ではありませんか？ですから、整数値を扱うとき、私の考えでは「1 mod n」は常に1であるため、「nを法とする1の自明でない平方根」が何であるかについて混乱しています。私は何が欠けていますか？