5

任意のサイズのデータ​​型にGMP（MPIR付き）を使用しています。ミラーラビン法を使用する素数判定関数も使用していますが、正確ではありません。これは私が修正したいものです。

平方根アプローチでブルートフォースを使用することにより、番号18446744073709551253が素数であることを確認できました。

素数であるかどうかを100％の精度でチェックする方法はありますか？

  • あまり多くのメモリ/ストレージスペースを使用するべきではありません。数メガバイトが許容されます。

  • 私が使用したsqrtメソッドよりも高速である必要があります。

  • サイズが64ビット以上の数値で機能するはずです。

  • 最後に、100％正確である必要があります。

私のオプションは何ですか？

私はブルートフォース方式（64ビット数の場合）で生きることができましたが、興味深いことに、より速く、より大きくしたいと思っています。また、64ビットの数値チェックは遅すぎました：合計43秒！

4

4 に答える 4

6

非常に大きな数の場合、AKS 素数性テストは O(log 7.5 n log log n) の時間で実行される決定論的素数性テストです。ここで、n は対象の数です。これは、O(√n) アルゴリズムよりも指数関数的に高速です。ただし、アルゴリズムには大きな定数係数があるため、数値がかなり大きくなるまで実用的ではありません。

お役に立てれば！

于 2012-12-11T22:07:04.193 に答える
3

一般的なポイントとして、物理コンピューターでは 100% の確実性は不可能です。これは、一部のコンポーネントが目に見えない障害を起こし、最後に与えられた答えが正しくない可能性が小さいながらも有限であるためです。その事実を考えると、十分な確率論的 Miller-Rabin テストを実行して、数値が合成される確率がハードウェアが故障する確率よりもはるかに低くなるようにすることができます。2^256 分の 1 レベルの確実性をテストすることは難しくありません。

boolean isPrime(num)
  limit <- 256
  certainty <- 0
  while (certainty < limit)
    if (millerRabin returns notPrime)
      return false
      exit
    else
      certainty <- certainty + 2
    endif
  endwhile
  return true
end isPrime

これは、2^256 分の 1 の確実性まで、数が素数であることをテストします。各 MR テストは、確実性に 4 倍の係数を追加します。私は、「産業力素数」と呼ばれる結果として得られる素数を見てきました。これは、すべての実用的な目的には十分ですが、理論的な数学的確実性には十分ではありません.

于 2012-12-12T13:23:04.033 に答える
1

証明方法は、証明しようとしている素数の種類 (たとえば、メルセンヌ素数には、素数を証明するための特別な方法があり、メルセンヌ素数だけで機能します) と 10 進数のサイズによって異なります。何百もの数字を見ている場合、解決策は 1 つしかありませんが、不十分ではありますが、AKS アルゴリズムです。十分な大きさの素数に対しては、他の素数性証明アルゴリズムよりも高速であることが証明されていますが、実際に役立つようになるまでには非常に時間がかかるため、実際に問題を起こす価値はありません。

大きな数の素数性の証明は、まだ十分に解決されていない問題です。もしそうなら、EFF賞はすべて授与され、暗号化は素数のリストではなく、素数を見つけるために使用される方法にいくつかの問題を抱えることになります.

近い将来、事前に生成された n の平方根までの素数のリストに依存せず、総当たり法を行わない、素数性を証明するための新しいアルゴリズムが登場すると私は信じています。平方根の下のすべての素数 (および多くの非素数も) が n の素数性の証人として使用されるようにします。この新しいアルゴリズムはおそらく、解析的数論で使用されるものよりもはるかに単純な数学の概念に依存するでしょう。素数にはパターンがあり、それは確かです。これらのパターンを特定することは、まったく別の問題です。

于 2012-12-16T07:22:46.537 に答える
1

nが小さい場合、試行分割が機能します。制限はおそらく 10^12 前後です。幾分大きなnについては、さまざまな Miller-Rabin 基底のコレクションの最小の擬素数を計算するさまざまな研究 (Gerhard Jaeschke と Zhou Zhang の作品を参照) があります。それはあなたを約10 ^ 25に連れて行きます。その後、物事は難しくなります。

素数性証明の「大砲」は、APRCL 法 (ヤコビ和またはガウス和と呼ばれる場合があります) と ECPP 法 (楕円曲線に基づく) です。どちらも複雑なので、独自の実装を作成しないでください。これらの方法はどちらも数百桁の数字を扱うことができます。

AKS 法は多項式時間であることが証明されており、簡単に実装できますが、比例定数が非常に高く、実際には役に立ちません。

n -1を因数分解できる場合、または部分的に因数分解できる場合でも、Pocklington の方法でnの素数を判断できます。ポックリントンの方法自体は速いですが、素因数分解はそうではないかもしれません。

これらすべてについて、数を証明する前に、その数が素数であることを合理的に確認する必要があります。数が素数でない場合、これらのメソッドはすべてそれを正しく判断しますが、最初に合成数が素数であることを証明しようとして多くの時間を浪費します。

私のブログにはAKSとPocklingtonの実装があります。

于 2012-12-12T14:01:31.347 に答える