C＃隨機BigInt有發電機

Question

我即將實現DSA algorithm，但有一個問題：

選擇 「P」，帶L位的素數，其中512 < = L < = 1024 L是64的倍數

我該如何實現該數字的隨機生成器？ Int64具有「僅」63位長度。

Answer 1

您可以生成一個隨機數使用此代碼n位：

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

BigInteger p = new BigInteger(bytes); 

的結果，當然，隨機的，不一定是一個素數。在.NET 4.0框架中引入了BigInteger class。

---

爲了產生大的素數，Wikipedia says：

對於在密碼學中使用的大素數，它是通常使用篩分的修飾形式：的奇數數字的隨機選擇的範圍期望的大小針對多個相對較小的奇素數（通常是小於65,000的所有素數）進行篩選。剩下的候選素數按隨機順序進行測試，使用標準素性測試，如可能的素數的Miller-Rabin素性測試。

所以你可以做這樣的事情：

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