問題タブ [primality-test]

Rosetta Code から抜粋したコードを使用しました。いくつかの名前を変更しましたが、実際には何も変更していません。

これは、いくつかの疑似コードと非常によく一致します。ただし、番号をテストすると

123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901

戻りますFalse。Miller-Rabin の他の (python および java) 実装はTrue、おそらく素数を返します。いくつかのテストの後、ラウンドのみの後にtry_composite戻ります! エラーを知りたいのですが、インデントが間違っているか、知らない機能があると思います。True2

ミラー・ラビンの素数性検定が確率論的であることは知っています。ただし、エラーの余地のないプログラミングタスクに使用したいと考えています。

long long入力数値が 64 ビット整数 (つまりC)の場合、非常に高い確率で正しいと仮定できますか?

以下に示す Verilog コードをコンパイルしようとすると、エラー メッセージが表示されます。ポイントは、入力を操作しようとしているということです。これは、Verilog では実行できないことがわかっている限りです。ポイントは、Verilog で次の条件を確認する必要があることです。

現時点では、次のコードがあります。

また、素数を 6n+1 または 6n-1 の形式でテストする必要があることに注意してください。コードでは、0 と 1 も素数であると想定する必要があります。

上記のコードを試してみると、次のようなエラー メッセージが表示されます。

強化された FOR ループが Verilog で有効になっていない

誰かがエラーを解決し、Verilog でロジックを完成させるのを手伝ってくれたら嬉しいです。

Haskell で Miller Rabin テストを実装しました。たとえば、ウィキペディアの Miller Rabin テストのエントリに示されている疑似コードに厳密に従おうとしました。今、私はオンラインで、特定の証人の選択について、テストが特定の範囲まで決定論的であることを発見しました。私は 2^64 未満の素数に興味があるので、この投稿で十分な境界を見つけまし た。. ただし、コードは、私がテストしたほとんどの小さな素数では機能するようですが、いくつかの大きな素数では失敗します。たとえば、10 桁の素数 5915587277 を試したところ、テストは false を返しました。私の実装は正しいと思いますが、誰かがどこで私が間違いを犯し、MR テストについて何かを誤解したかを見つけてくれることを願っています。助けてくれてありがとう。また、乱雑なコードで申し訳ありません。

入力が素数であるかどうかを計算しようとしていますが、何か問題が発生しています...これが私のコードです:

false毎回与えてくれます。私が間違っていることについて何か手がかりやアイデアを得た人はいますか?

したがって、次のことを検証する n 番目の数を見つける問題を解決する必要があります。それは 2 つの連続する素数の合計であり、整数の平方根を与えます。私の問題は、エラトステネスのふるいがメモリを使いすぎて、素数の素朴なチェックが遅すぎることです。これを高速かつメモリを追加せずに解決する方法はありますか? フェルマーの定理を使ってみましたが、遅いことがわかりました。

前もって感謝します。

私は Java で Miller-Rabin 確率検定を実演するプログラムを書いています。コードはかなり完成しました...

問題を示すために、値として 86 をハードコーディングしました。a を m に増やし、法 n をとって初めて b を計算するところは、計算が正しくありません。86^19 % 153 に対する正しい答えである 86 の b0 を与える代わりに、b0 は 107 に等しくなります。デバッガーで自分の値をチェックしましたが、それらは正しいです。a^m の値も確認したところ、86^19 が得られたので、モジュラス部分で問題が発生しました。残念ながら、何が数学を台無しにしているかわかりません。