0

任意の数が素数であることを証明できるアルゴリズムを探しています。大きい数とは、10 進数が少なくとも 1 億桁あり、メルセンヌ素数などの単純な数式では表現できない数を意味します。

ここに私の要件があります：

1- 完全に正しい必要があります

2-基本的な家庭用コンピューターで実行可能である必要があります

3-数週間または数か月以内にコースを完了する必要があります。

私のメモリ制限は、1 TB のハード ドライブを搭載した専用マシンで 8 GB の RAM です (使用可能なキャッシュの量をオプションで設定できます)。数ヶ月かけて順番に検討していきます。

編集 1: 現在の方法ではほとんど不可能ではないにしても、これが競争するのが難しい分野であることは十分承知しています。私は現在の方法を使用していません。非常に大きな数に対して私の方法が正しいことを証明する方法が必要です。

Edit2: 非確率的方法が必要な理由の 1 つは、これが EFF 賞への試みであり、そこで成功すると、2 番目の EFF 賞になるからです。私の方法が正しければ (それは 1 つのクラクション IF です)、私のノート PC ですべてのことを実行できるはずです。

4

1 に答える 1

1

私が理解していることから、あなたは次のようなアルゴリズムを探しています。

  • 決定論的
  • かなり速い
  • かなり合理的なメモリフットプリントで

最後の部分は（まだ）実装しようとしたことがないのでわかりませんが、素数問題は一般的な数値で解決されたことは知っています。つまり、形式に関係なく、100％確実に数が素数であるかどうかを判断できます。この問題を解決する最初の既知のアルゴリズムであるAKS素数性テストを確認する必要があります。

おっしゃるように、実行には時間がかかる場合がありますが、最終的には特定の答えで終了します。最適化されたバージョンの複雑さはO（（log n）^ 7.5です（log nはnの桁数に比例します）。

ただし、このランタイムはかなり大きく、多くの数値をテストする必要があるため、最初に、より高速で非決定論的なアルゴリズムを使用してそのような数値をフィルタリングすることを検討する必要があります。言い換えれば、私はミラーラビンテストを実行しようとしますいくつかの数値の場合（a = 2,3,5,7、..。-最初の10個の素数で十分ですが、より高い精度が本当に必要な場合でも、おそらく50個の素数を超えてはなりません）。私が正しく覚えていれば、k個のミラーラビンテストの後でテストされた数が偽素数である確率は1/4^k未満です。言い換えると、少数のテストを実行でき（これらのテストは非常に高速であることは言うまでもありません）、その数が素数であるかどうかに非常に自信があります（これらのテストのいずれかが失敗した場合、その数は間違いなく素数ではありません）。すべてのMRテストに合格したら、確認のためにテストされた番号に対してAKSアルゴリズムを実行します（MR wikipediaページで確認できるように、いくつかのテストを実行した後の最小の誤検知は非常に速い速度で増加します）。

于 2012-11-22T05:49:58.117 に答える