問題タブ [primes]

私は遊んでいて、RSAの実装を書き込もうとしています。問題は、キーペアの生成に関係する大量の素数の生成に固執していることです。誰かが私に巨大な素数/確率的素数を生成するための速い方法を教えてもらえますか？

ウラムのスパイラルを無限に大きくするためのアイデア/コード（できればC＃ですが、他の言語も機能します）を探しています（プログラムの実行時間の長さ、または停止するまで制限されます）。

現在、数値はすべて素数であるため、それらのコードはかなり無関係です。興味深いのは、増え続ける (無限の) スパイラルでの配置をどのようにコーディングするか、それをサポートするにはどのようなデータ構造が適しているか、そしておそらく出力のアイデア (グラフィック ファイル、テキスト ファイル?) です。

これについてどう思いますか？

数値を素因数分解するために次のプログラムを作成しました。

以下は私が得る出力です：

Altho'、戻り値は適切に出力されますが、戻り値の後は常に何も出力されないようです。私は何が欠けていますか？

また、プログラムを改善するにはどうすればよいですか（再帰を引き続き使用します）

私の問題は(g^x) mod p、JavaScript ですばやく計算することです。^指数modはモジュロ演算です。すべての入力は非負の整数で、x約 256 ビットあり、p2048 ビットの素数であり、g最大 2048 ビットの場合があります。

JavaScript でこれを実行できるソフトウェアのほとんどは、JavaScript BigInt ライブラリ ( http://www.leemon.com/crypto/BigInt.html ) を使用しているようです。このライブラリでこのようなサイズの累乗を 1 回実行すると、遅いブラウザ (Firefox 3.0 と SpiderMonkey) で約 9 秒かかります。少なくとも 10 倍高速なソリューションを探しています。二乗と乗算 (二乗によるべき乗、http://en.wikipedia.org/wiki/Exponentiation_by_squaring ) を使用するという明白なアイデアは、2048 ビットの数値には遅すぎます: 最大 4096 の乗算が必要です。

ブラウザのアップグレードはオプションではありません。別のプログラミング言語を使用することはオプションではありません。番号を Web サービスに送信することはできません。

実装されているより高速な代替手段はありますか?

更新:以下の outis の回答に記載されている記事http://www.ccrwest.org/gordon/fast.pdfで推奨されているように、いくつかの追加の準備 (つまり、数百乗の事前計算) を行うことで、2048-最大で 354 のモジュラ乗算のみを使用するビット モジュラべき乗。(従来の平方乗算法は非常に遅く、最大 4096 の剰余乗算を使用します。) そうすることで、累乗剰余を Firefox 3.0 では 6 倍、Google Chrome では 4 倍高速化します。4096/354 の完全な高速化が得られない理由は、BigInt の累乗剰余アルゴリズムが、モンゴメリー削減 ( http://en.wikipedia.org/wiki/Montgomery_reduction )を使用するため、2 乗乗算よりも既に高速であるためです。 .

更新: BigInt のコードから始めて、手動で最適化された (およびインライン化された) カラツバ乗算 ( http://en.wikipedia.org/wiki/Karatsuba_algorithm ) の 2 つのレベルを実行する価値があるように思われ、その後でベース 32768 O( n^2) 乗算は BigInt で実装されます。これにより、2048 ビット整数の乗算が 2.25 倍高速化されます。残念ながらモジュロ演算は速くなりません。

更新: http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf で定義されている修正された Barrett リダクションと、からつばの乗算と事前計算の累乗 ( http://www.ccrwest.org/gordon/で定義されている) を使用します。 fast.pdf )、Firefox 3.0 では、1 回の乗算に必要な時間を 73 秒から 12.3 秒に短縮できます。これは私ができる最善のようですが、それでも遅すぎます。

更新: Flash Player の ActionScript 2 (AS2) インタープリターは、Firefox 3.0 の JavaScript インタープリターよりも遅いように見えるため、使用する価値がありません: Flash Player 9 の場合は 4.2 倍遅く、Flash Player の場合は10、2.35倍遅いようです。数値計算における ActionScript2 と ActionScript3 (AS3) の速度の違いを知っている人はいますか?

更新: Flash Player 9 の ActionScript 3 (AS3) インタープリターは、JavaScript int Firefox 3.0 とほぼ同じ速度であるため、使用する価値はありません。

更新: Flash Player 10 の ActionScript 3 (AS3) インタープリターは、 の代わりに を使用し、intの代わりに を使用すると、Firefox 3.0 の JavaScript インタープリターよりも最大 6.5 倍高速になります。少なくとも、2048 ビットの大きな整数の乗算では 2.41 倍高速でした。そのため、可能な場合は Flash Player 10 で実行して、AS3 でべき乗剰余を実行する価値があるかもしれません。これは、Google Chrome の JavaScript インタープリターである V8 よりもまだ遅いことに注意してください。さまざまなプログラミング言語と JavaScript の実装の速度比較については、http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.htmlを参照してください。NumberVector.<int>Array

Update: There is a very fast Java solution, which can be called from the browser's JavaScript if the Java plugin is installed. The following solution is about 310 times faster than the pure JavaScript implementation using BigInt.

Can anyone translate this code to Silverlight (C#)?

私は現在sparcコンピュータを使用しており、数値が素数であるかどうかを調べようとしています。

ここにコードの一部があります：

つまり、基本的にここにあるのは3/2です。したがって、1のリマインダーがあるはずです。このリマインダーは％Yレジスターに入れる必要があります。しかし、％Yを見ると、まだ0のままです。％Yがまだ0のままであるのに、1のリマインダーが表示されるのはなぜですか。

私は整数を取り、ブール値を返し、その数が素数であるかどうかを示すメソッドを考え出そうとしていますが、Cについてはよくわかりません。誰かが私にいくつかのポインタを教えてくれませんか？

基本的に、私は次のようにC＃でこれを行います：

ここの誰かが共有したいアトキンのふるいの良い実装を持っているかどうか疑問に思いました。

私はそれを実装しようとしていますが、頭を完全に包むことができません。これが私がこれまでに持っているものです。

ウィキペディアにリストされている擬似コードを「翻訳」しようとしたところですが、正しく機能していません。ですから、私は何かを誤解したか、何か間違ったことをしただけです。またはおそらく両方...

テストとして使用する最初の500素数のリストがあり、実装は40番（または41番？）で失敗します。

値はインデックスで異なります[40]
期待値：179
しかし、だった：175

私の間違いを見つけることができますか、共有できる実装がありますか、またはその両方ですか？

私が使用している正確なテストは次のようになります。

これが可能かどうかはわかりませんが、質問する必要があります。私の数学的およびアルゴリズムのスキルは、ここで私を失敗させているようなものです:P

問題は、特定の制限まで素数を生成するこのクラスがあることです。

今、私が望むのは、シーケンスが（理論的に）決して停止しないように制限を取り除くことです。

私はそれが次のようになると考えています：

1. 些細な制限から始める
   • 極限までのすべての素数を見つける
   • 新たに見つかったすべての素数を生成する
   • 制限を増やす (古い制限を 2 倍または 2 乗するなどして)
   • ステップ 2 に進む

そして、最適には、そのステップ 2 は古い制限と新しい制限の間でのみ機能する必要があります。言い換えれば、最低の素数を何度も見つける必要はありません。

これを行う方法はありますか？x私の主な問題は、yたとえばこのアルゴリズムの内容がよくわからないことです。同様に、同じ種類のアルゴリズムを使用して、xandyをoldLimit(最初は 1) に設定し、それを まで実行できnewLimitますか? または、それはどのように機能しますか？これに光を当てる明るい心はありますか？

これのポイントは、その制限を設定する必要がないようにすることです。たとえばTake()、制限が十分に高いかどうかなどを気にせずに、Linq と必要な数の素数を使用できるようにします。

与えられた数に最も近い素数を見つけるための素晴らしいアルゴリズムはありますrealか？最初の100素数程度で検索するだけです。

現在、私はたくさんの素数を配列に格納していて、一度に1つの数の差をチェックしています（O（n）？）。