11

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

4

5 に答える 5

19

素数を正確に生成するわけではありません。大きな奇数をランダムに生成し、その数が素数かどうかをテストし、そうでない場合は別の数をランダムに生成します。ランダムな試行で素数を「ヒット」する確率は (2/ln n) であると基本的に述べている素数の法則がいくつかあります。

たとえば、512 ビットの乱数の素数が必要な場合は、2/(512*ln(2)) の中に 1 つが見つかります。したがって、試行する数の 177 のうち、およそ 1 つが素数になります。

数値が素数であるかどうかをテストする方法は複数ありますが、この質問に対する別の回答で述べられているように、良い方法の 1 つは「Miller-Rabin テスト」です。

また、OpenSSL には素数をテストするための便利なユーティリティがあります。

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
于 2009-07-20T23:57:27.160 に答える
3

TrueCryptがどのようにそれを行うかを見てください。また、大きな擬素数をテストするためのRabin-Millerを見てください。

于 2009-07-18T00:31:12.170 に答える
3

U. Maurer によるアルゴリズムがあり、特別なサイズのすべての素数のセットにほぼ均一に分布するランダムな証明可能な (統計的に確率の高いものとは対照的に) 素数を生成します。私はかなり効率的な Python 実装を持っています: http://s13.zetaboards.com/Crypto/topic/7234475/1/

于 2015-01-20T11:36:05.413 に答える
2

使用している言語については言及していません。これを行うメソッドが組み込まれているものもあります。たとえば、Javaでは、BigIntegerでnextProbablePrime（）を呼び出すのと同じくらい簡単です。

于 2009-07-18T00:32:19.427 に答える
1

Mono には、Java と同様にオープン ソースの BigInteger クラスがあります。あなたはそれらを見ることができます。それらはおそらく移植可能です:) g'luck

于 2009-07-20T07:34:16.463 に答える