c# - C# ランダム BigInt ジェネレーター

Question

DSA アルゴリズムを実装しようとしていますが、問題があります。

512 <= L <= 1024 で、L が 64 の倍数である L ビットの素数 "p" を選択します。

その数の乱数発生器を実装するにはどうすればよいですか? Int6463ビット長「のみ」です。

Answer 1

n次のコードを使用して、ビットで乱数を生成できます。

var rng = new RNGCryptoServiceProvider();
byte[] bytes = new byte[n / 8];
rng.GetBytes(bytes);

BigInteger p = new BigInteger(bytes);

もちろん、結果はランダムであり、素数である必要はありません。

BigInteger クラスは、.NET 4.0 Framework で導入されました。

---

大きな素数を生成するために、ウィキペディアは次のように述べています。

暗号化で使用される大きな素数については、通常、ふるい分けの修正された形式を使用します。目的のサイズのランダムに選択された範囲の奇数が、いくつかの比較的小さな奇数の素数 (通常はすべて 65,000 未満の素数) に対してふるいにかけられます。残りの素数候補は、可能性のある素数に対するミラー-ラビン素数性検定などの標準的な素数性検定を使用して、ランダムな順序で検定されます。

したがって、次のようなことができます。

var p = Enumerable.Range(0, numberOfCandidates)
                  .Select(i => RandomOddNumber(bits))
                  .Where(x => !primesLessThan65000.Contains(x))
                  .Where(x => PrimalityTest(x))
                  .FirstOrDefault();