問題タブ [primes]

私はPythonで暗号化スキームをシミュレートしています。私はそれに対する新しいユーザーです。

p = 512ビット数であり、その最大の素因数を計算する必要があります。私は2つのことを探しています。

1. この大規模な素因数分解を処理するための最速のコード
2. 512ビットの数値を入力として受け取り、それを処理できるコード。

私は他の言語でさまざまな実装を見てきました。私のコード全体はPythonであり、これが私が立ち往生している最後のポイントです。それで、Pythonに実装があるかどうか教えてください。

私はPythonの新規ユーザーなので、簡単に説明してください

英語が下手でごめんなさい。

編集（以下のOPの回答から取得）：

上記のコードは「1238162376372637826」に対して（少し遅れて）機能しますが、

10902610991329142436630551158108608965062811746392 57767545600484549911304430471090261099132914243663 05511581086089650628117463925776754560048454991130443047

Pythonを狂わせます。上記のように、すぐに計算してもらう方法はありますか？

ユーザー入力に基づいて素数を生成しようとしています。これは私がこれまでに持っているものですが、私はそれを理解できないようです:

与えられた数よりも大きい最小の素数を見つけるにはどうすればよいですか？たとえば、4の場合、5が必要です。7が与えられると、11が必要です。

これを行うための最良のアルゴリズムに関するいくつかのアイデアを知りたいです。私が考えた方法の1つは、エラトステネスのふるいを通して素数を生成し、与えられた数の後に素数を見つけることでした。

Project Eulerの問題7をやっています。私がすべきことは、10,001 番目の素数を計算すること^です。(素数とは、それ自体と 1 だけで割り切れる 1 より大きい整数です。)

これが私の現在のプログラムです：

100^番目の素数などの検索では問題なく動作しますが、非常に大きな入力 (10,001 など) で実行すると、スタック オーバーフローが発生します。なぜ、どうすればこれを修正できますか?

このアプリケーションは、番号「n」を受け取ります。この数を受け取った後、プログラムは素数のリストの n 番目の素数を表示する必要があります。たとえば、ユーザーが「3」と入力すると、5 は 2 から始まる 3 番目の素数であるため、プログラムは「5」を表示するはずです。コードに問題があることはわかっていますが、どこに問題があるのか​​ わかりません。どうすれば修正できますか。

Aが与えられた場合、10 ^ 20のオーダーで、Aより大きい最初のいくつかの素数のリストをすばやく取得したいと思います。OK、私のニーズはそれほど正確ではありません。合成数になることがある場合は問題ありません。リストにあります。

Aより大きい（確率的）素数を列挙する最も速い方法は何ですか？

Aより大きいすべての整数（たとえば、2と3の明らかな倍数を除く）をステップスルーして、それぞれに対して素数性テストを実行するよりも速い方法はありますか？そうでない場合、そして唯一の方法が各整数をテストすることである場合、どの素数性テストを使用する必要がありますか？

本当に大きい (long long の範囲内の) 数値間の間隔で素数性をテストする必要があるため、数値が素数かどうかを確認するための高速なアルゴリズムが必要です。あなたのアイデアを提案してください。

この記事には次のように書かれています。

すべての素数は、 、 、 、または一部の として表す 30k±1こと30k±7が30k±11でき 30k±13ますk。つまり、30 個の数値ごとに 8 ビットを使用して、すべての素数を格納できます。100 万個の素数を 33,334 バイトに圧縮できます

「つまり、すべての素数を格納するために、30 個の数値ごとに 8 ビットを使用できるということです」

この「30個の数字あたり8ビット」はkの場合ですよね？しかし、各k値は必ずしも 1 ビットだけを占めるわけではありません。代わりに8 つの k 値であるべきではありませんか?

「100 万個の素数を 33,334 バイトに圧縮できます」

これがどのように真実なのかわかりません。

次の 2 つのことを示す必要があります。

• k の値 (任意に大きくすることができます)

• 8 つの州のうちの 1 つの STATE(-13,-11,-7,-1,1,7,11,13)

「33,334 バイト」がどのように に到達したかについては詳しく説明していませんが、1 つ言えることは、素数がどんどん値が大きくなるにつれて、kの値を格納するためにより多くのスペースが必要になるということです。

では、「33,334 バイト」に修正するにはどうすればよいでしょうか。

すべての素数をファイルに書き込むプログラムを作成したいと思います（人気のあるアルゴリズム「エラトステネスのふるい」があることは知っていますが、自分で作成しようとしています）。まだ値が1であるバイトのすべての複雑さを排除し、それらをファイルに書き込もうとしています。

私は、RSA に関する元の論文で提示された Solovay-Strassen 素数性テストをプログラムする予定です。

さらに、小さな bignum ライブラリを作成する必要があるため、bignum の便利な表現を探しているときに、次の仕様に出会いました。

また、カラツバ法を使用した乗算ルーチンも作成します。

だから、私の質問のために：

bignum 構造体に整数データを格納するには、どのベースが便利でしょうか?

注: GMP などの bignum にサードパーティまたは組み込みの実装を使用することは許可されていません。

ありがとうございました。