C#随机BigInt生成器

本文介绍了C#随机BigInt生成器的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我即将实现 DSA算法，但是存在问题:

I'm about to implement the DSA algorithm, but there is a problem:

选择"p"，它是L位的质数，其中512< = L< = 1024，L是64的倍数.

choose "p", a prime number with L bits, where 512 <= L <= 1024 and L is a multiple of 64

如何实现该数量的随机生成器? Int64的长度只有63位.

How can I implement a random generator of that number? Int64 has "only" 63 bits length.

推荐答案

您可以使用以下代码生成带有n位的随机数:

You can generate a random number with n bits using this code:

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

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

The result is, of course, random and not necessarily a prime.

引入了 BigInteger类在.NET 4.0 Framework中.

The BigInteger class was introduced in the .NET 4.0 Framework.

要生成大素数，维基百科说:

对于密码术中使用的大质数，通常使用改进的筛分形式:将所需大小的奇数随机选择范围与相对较小的奇数质数(通常所有质数小于65,000).其余候选素数按标准的素数检验(例如Miller-Rabin素数检验)以随机顺序进行测试，以检验可能的素数.

For the large primes used in cryptography, it is usual to use a modified form of sieving: a randomly-chosen range of odd numbers of the desired size is sieved against a number of relatively small odd primes (typically all primes less than 65,000). The remaining candidate primes are tested in random order with a standard primality test such as the Miller-Rabin primality test for probable primes.

因此您可以执行以下操作:

So you could do something like this:

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