c# - C# 随机 BigInt 生成器

Question

我即将实现DSA算法，但是有一个问题：

选择“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);

结果当然是随机的，不一定是素数。

BigInteger 类是在 .NET 4.0 框架中引入的。

---

为了生成大素数，维基百科说：

对于密码学中使用的大素数，通常使用一种改进的筛选形式：随机选择的所需大小的奇数范围与一些相对较小的奇素数（通常所有质数小于 65,000）进行筛选。剩余的候选素数通过标准素数测试以随机顺序进行测试，例如对可能素数的米勒-拉宾素数测试。

所以你可以做这样的事情：

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