本当に大きな素数を生み出します
https://stackoverflow.com/questions/1146274
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は遊んでいて、RSAの実装を書こうとしています。問題は、キーペアの生成に関与する大規模な素数を生成することに固執していることです。誰かが私に、巨大なプライム/可能性のある素数を生み出すための迅速な方法を指し示すことができますか？
解決
素数を正確に生成しません。ランダムに大きな奇数を生成し、その数がプライムかどうかをテストします。基本的に、ランダムトライを介してプライムを「打つ」というあなたのオッズは（2/ln n）と基本的に述べているいくつかの主要な法則があります
たとえば、512ビットのランダムプライム番号が必要な場合、2/（512*ln（2））に1つが見つかります。
数字がプライムかどうかをテストする方法は複数あり、1つは「ミラーラビンテスト」です。 この質問に対する別の答えで述べたように.
また、OpenSSLには、プライムをテストするための優れたユーティリティがあります。
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
他のヒント
方法を見てください TrueCrypt それをします。また、見てください rabin-miller 大規模な偽物をテストするため。
使用している言語については言及しませんでした。これを作成する方法がある人もいます。たとえば、Javaでは、これは呼び出しと同じくらい簡単です nextProbablePrime（） Bigintegerで。
前の答えは正しくありません：2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59。
ポスターは、数え切れないほどのプライムナンバーがあるという（実際の）証拠を誤って覚えていると思います。
Monoには、Javaと同様にオープンソースであるBigintegerクラスがあります。それらを見ることができます。彼らはおそらくポータブルです:) g'luck
U. Maurerのために、特別なサイズのすべての素数のセットにほぼ均一に分布しているランダムな（統計的に高度に推進可能な）プライムを生成するアルゴリズムがあります。 Pythonの実装があります。http://s13.zetaboards.com/crypto/topic/7234475/1/
