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();