問題タブ [primality-test]

インターネットでこのソリューションを見つけましたが、それを理解するための助けが必要です:

いくつかのこと：

私の理解では、フォールド関数のアキュムレータが a の場合Boolean、ラムダ関数自体に設定する必要があります。何かのようなもの：

しかし、ここではそうではありません。

また、使用されている範囲にprimesは終了番号がありません。これが機能する理由は Haskell の遅延評価によるものであることはわかっていますが、ここではどのように機能しているのでしょうか?

最後に、この関数は適切なブール値を返すようには見えません。素数とは、自身と 1 以外に約数がないものです。

私は完全に混乱しています。私を助けてください。

私は Java で Miller-Rabin 素数性テストを実装し、その計算時間をBigIntegerクラスのネイティブな素数性テストと対峙させようとしていました。私がここにいることを考えると、おそらく私のコードが機能しないと推測したでしょう。問題は、私が得たエラーが、Lady Math が不可能だと言っているものだということです。私が間違っていることを知りたいです。

Miller-Rabin 素数性テストの背後にある考え方は、多くの数学を必要とせずに、すべての素数が妥当性を満たすというものです。その正当性が満たされない場合、その数は合成されます。ただし、妥当性が満たされている場合、その数は素数であるか、疑似素数と呼ばれる合成数のサブセットに属している可能性があります。絶対に起こり得ないことは、素数がテストによって複合として認識されることです。
これはまさに、コードの実行中に時々起こることです。

コードで数学エラーを検索しましたが、何もないと思います。Java の間違いを探してみましたが、何も見つかりませんでした。明らかに、私が見ていない何か (または多くの何か) があるので、助けを求めたいと思います。

以下はmain、Miller-Rabin テストの実装を格納するためだけに作成された静的クラスですmain。これは確率論的テストではなく、決定論的テストです。このメソッドは、可能なすべての証人を検索し、見つかった場合は返しますfalse(つまり、素数ではありません)。それ以外の場合は を返しますtrue。

編集: 次の行は methodlog(x,base)です。

ウィキペディアでは、以下のアルゴリズムは、奇数の整数 n が確率論的ラビン・ミラー素数性テストによって合成されているかどうかをテストすることになっています。

以下の GitHubの BigIntANSForth でのアルゴリズムの実装は、間違っている可能性があります。プレフィックス 'b' は 'big' を表します。大きい数値用のパラメーター スタックと、余分な大きい数値スタック 'bx' があります。また、'ys' は 1 つのセル整数の追加スタックです。

バーのプレフィックスは「バレット削減」を表します。

835681365813571357135731057315713857138571305713011111111111111111111112429 は、任意の精度の実装による合成ですが、Wolfram Alphaによる素数です。

アルゴリズムを正しく解釈したかどうかはわかりません。なにか提案を？

RSAアルゴリズムを作ろうとしています。そのためには、rabin-miller+witness+modular exponentiation が必要です (少なくとも、それを使用する必要があります)。問題は、乱数を生成して素数であるかどうかをラビン・ミラーで確認するときに発生し、その結果、非素数がラビン・ミラー・アルゴリズムで素数になります。誰かが私がどこで失敗したかを確認するために手を貸してくれませんか. 前もって感謝します。

次のコードは、ユーザーが入力した数値が素数かどうかを示す出力を示しています。

上記のコードは私のものではなく、毎回素数を正しく識別します (つまり、 else句のprintfステートメントが出力されます)。

ifステートメントについての私の理解では、if-elseステートメントのelse句は、 else句がまだない最も近いifステートメントに属します。そうは言っても、上記のコードのelse節は最も近いifステートメントに属していると思います。

私の質問は次のとおりです。ユーザーが 31 や 37 などの素数を入力した場合、 else句のprintfステートメントはどのように出力されるのでしょうか? (2 番目のifステートメントの) 条件は、b が だけインクリメントされることを考慮すると、常に true になります。したがって、ユーザーが数値 31 を入力すると、変数bは 30 にインクリメントされるだけです。ユーザーが入力した数値が素数であるかどうかに関係なく、2 番目のifステートメントのprintfステートメントが出力されることはありません。条件が常に真になることを考えると、そうではないでしょうか？if (b<a)(a-1)if (b<a)

上記のコードはどのようにしてすべての素数を正しく出力し、それで問題なく動作するのでしょうか? （ if文の仕組みについての私の限られた理解によれば、そうすべきではありません）

def 繰り返し (m、結果、a、s、d):

少なくとも 100 桁の数字など、非常に大きな数字をテストするには、素数テストの Python プログラムを作成する必要があります。上記のコードは、繰り返される 2 乗に対する Miller Rabin 決定論的素数性テストのコードの一部です。多数の場合、動作が非常に遅くなります。どうすれば高速化できますか？プロジェクト用です。ありがとう！

Miller-Rabin 検定では、k個の乱数整数を使用して素数性を検定します。

CLRS、第 3 版、971 ページによる^と:

定理 31.38

n が奇数の合成数である場合、n の合成数の証人の数は少なくとも (n - 1)/2 です。

それでは、ランダムなテストを k 回実行する代わりに、異なる( n - 1 ) / 2 の値を使用してそれらの素数性をテストしてみませんか? 2 を除くすべての素数は奇数であり、目撃者は少なくとも ( n - 1 ) / 2 ではないため、存在する場合、目撃者を見つけることが保証されます。

私は試行分割の素数性テストの基本を行っていたので、それをコードに実装しました。アルゴリズムのパフォーマンスは、次のような多くのトリックを使用して向上させることができます。

1) 平方根 (n) までの試行分割のみを実行する

2) 平方根 (n) までのふるいを作成し、作成したふるいの素数に対してのみ試行除算を実行することにより、メモリを時間と交換します。

しかし、(n mod 6) の値が ( 6k +/- 1 ルールを使用しn%6て) 判明した場合、結果を複合として返すという考えはどこにもありませんでした。1 or 5素数決定テストでこのルールを使用すると、パフォーマンスが向上しませんか? はいの場合、なぜそれがどこにも言及されていないのですか? いいえの場合、なぜそうなるのですか?

ありがとう。