問題タブ [primality-test]

を受け入れる非決定性チューリングマシンのプログラムを説明するように求められる宿題の問題がありますL = {a^n: n is prime}。どうすればいいのかわかりません。私はnを知っていますか？sを単項桁として使用してaカウントしますか？文字列を無視して、主にnをテストすることはできますか？またはプライム値がわかっているので、それらのセルの場所だけが状態を受け入れており、通常のようにデータを読み取ることができますか？

どうすればいいですか？

大学のプロジェクトで RSA 暗号システム アルゴリズムを実装したいと考えており、使用するプログラミング言語を決定しようとしています。私はCに非常に精通しているので、便利な選択です。ただし、アルゴリズムは非常に大きな数を処理する必要があり (Primality サブルーチンが含まれます)、Python を使用すると実装が改善されると聞いています。そうですか？

前もって感謝します。

だから私はHaskellに全く慣れていないので、あまり表示されないことを願っています。とにかく、私は数が素数であるかどうかを判断する関数を作成しようとしていました。基本的な考え方は次のとおりです。数値が与えられたら、それよりも小さい他の数値で割り切れるかどうかを確認します。その場合、falseを返します。そうでない場合、それは素数であり、trueを返します。これまでのコード（動作していることがわかっている）は次のとおりです。

生産：

sqrt（x）以下の値をチェックするだけでよいので、これを少し最適化したいと思います。問題は、これを実装しようとすると、物事がおかしくなることです。

それがひどいように見えるという事実（私は私が新しいと言った）に加えて、それは正しい結果を与えません：

何が変わったのかを理解しようとしています。理由は次のとおりです。

正しい番号を教えてくれているようです。これは小さな問題ですが、私は真剣に混乱しています...

FIPS 186-3 C.3.1の説明に従って、Miller-Rabin primality テストを実装しようとしています。私が何をしても、私はそれを機能させることができません。指示はかなり具体的で、何も見逃していないと思いますがtrue、非素数の値を取得しています。

私は何を間違えましたか？

これ：

私に与えている：

Haskell に入りました。与えたビット数に応じて素数を返す素数ジェネレーターを作成しようとしています。ある種のエラトステネスの篩を使用しますか? これが最速の方法でしょうか？現在、Miller-Rabin の素数チェッカーが既にあります。これを行う正しい方法と間違った方法はありますか？また、大量の数を非常に迅速に生成できるようにしたいと考えています。

元。32 ビットの素数を生成する

ここまでのコード。

RSA でのライブラリ関数の使用:

皆さん、ありがとう、私はあなたの助けに本当に感謝しています.

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

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

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

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

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

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

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

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

私はそれが何度も議論されてきたことを知っています。読んだのですが、どういうわけかわかりません。入力した数が素数かどうかを判断するプログラムを書きたい。

私がインターネットのどこかで見つけた実装の1つ：

ここにいくつかの質問があります：

• 上記ではi、とは何ですか。また、開始値がなぜ2ですか。
• i = i + 1このプログラムでは何をしますか？
• 'is a prime number.'インタプリタは、ボディループの外にある場合でも、いつ印刷するかをどのように知るのですか？

数値が素数かどうかを確認する正しい方法であるかどうかを尋ねたいと思いますか? 0 と 1 は素数ではないことを読んだからです。

演習として書いている RSA 実装の素数性テストを実装しようとしています。私は主に Rabin-Miller を使用していますが、1,000 未満のすべての素数のリストを定式化するエラトステネスのふるいを持っており、候補者がそのうちの 1 つを素因数として持っているかどうかを判断するための簡単なテストに使用します。

関連する機能は次のとおりです。

ここで、primeList は Sieve によって生成された素数のリストです。これは 2^55 程度の to_test 値までは完全に機能しますが、それを超えると、

このステートメントは、Rabin-Miller が素数であると判断した to_test を渡した場合でも、常に 0.0 と評価されます。これが何であるかわかりません。Python が非常に大きな数をどのように処理するかについては明確ではありませんが、私の知る限り、2^55 はオーバーフロー ボーダーのようなものではないようです。Sieve を使用すると、関数が大幅に高速になり、2048 ビットの実装のキーを生成するにはしばらく時間がかかるため、これは演習ですが、Sieve が機能するかどうかを確認したいと思います。

前もって感謝します。

ここにあります...

これは、 Miller-Rabin primality testに関するウィキペディアの記事から入手しました。しかし、私はそれを理解することができませんでした......私はその背後にある数学を理解しようとしているのではなく、プログラムに実装するだけです. このアルゴリズムは、ちょっとややこしいように思えます。より優れた、より単純な疑似コードまたは vb.net での実装が役立つでしょう。

これまでに書かれた編集コード: