考虑这种效果很好的方法：
public static bool mightBePrime(int N) {
BigInteger a = rGen.Next (1, N-1);
return modExp (a, N - 1, N) == 1;
}
现在，为了满足我正在学习的课程的要求，mightBePrime必须接受BigIntegerN，但这意味着我需要一种不同的方式来生成我的 random BigInteger a。
我的第一个想法是做类似的事情BigInteger a = (N-1) * rGen.NextDouble ()，但是 aBigInteger不能乘以 a double。
如何生成BigInteger1 和 N-1 之间的随机数，其中 N 是 a BigInteger？
Paul 在评论中建议我使用随机字节生成一个数字，如果它太大则将其丢弃。这是我想出的（马塞尔的回答+保罗的建议）：
public static BigInteger RandomIntegerBelow(BigInteger N) {
byte[] bytes = N.ToByteArray ();
BigInteger R;
do {
random.NextBytes (bytes);
bytes [bytes.Length - 1] &= (byte)0x7F; //force sign bit to positive
R = new BigInteger (bytes);
} while (R >= N);
return R;
}
http://amirshenouda.wordpress.com/2012/06/29/implementing-rsa-c/也有一点帮助。
使用随机类
public BigInteger getRandom(int length){
Random random = new Random();
byte[] data = new byte[length];
random.NextBytes(data);
return new BigInteger(data);
}
BigInteger在找到指定范围内的有效值之前，简单的实现平均会失败 64 次。
在最坏的情况下，我的实现平均只重试 0.5 次（读作：50% 的时间它会在第一次尝试时找到结果）。
此外，与模块化算术不同，我的实现保持了一个统一的分布。
我们必须在和BigInteger之间生成一个随机数。minmax
min > max我们交换minmax[min, max]到[0, max-min]，这样我们就不必处理符号位max包含 ( bytes.Length)zeroBits)bytes.Length字节序列< max，至少zeroBits从最高有效位开始的位必须为 0，因此我们使用 a对最高有效字节zeroBitMask进行单个位对位&操作来设置它们，这将节省大量时间通过减少生成超出我们范围的数字的变化> max，如果是，我们再试一次[0, max-min]将范围从[min, max]min我们有我们的号码。
public static BigInteger RandomInRange(RandomNumberGenerator rng, BigInteger min, BigInteger max)
{
if (min > max)
{
var buff = min;
min = max;
max = buff;
}
// offset to set min = 0
BigInteger offset = -min;
min = 0;
max += offset;
var value = randomInRangeFromZeroToPositive(rng, max) - offset;
return value;
}
private static BigInteger randomInRangeFromZeroToPositive(RandomNumberGenerator rng, BigInteger max)
{
BigInteger value;
var bytes = max.ToByteArray();
// count how many bits of the most significant byte are 0
// NOTE: sign bit is always 0 because `max` must always be positive
byte zeroBitsMask = 0b00000000;
var mostSignificantByte = bytes[bytes.Length - 1];
// we try to set to 0 as many bits as there are in the most significant byte, starting from the left (most significant bits first)
// NOTE: `i` starts from 7 because the sign bit is always 0
for (var i = 7; i >= 0; i--)
{
// we keep iterating until we find the most significant non-0 bit
if ((mostSignificantByte & (0b1 << i)) != 0)
{
var zeroBits = 7 - i;
zeroBitsMask = (byte)(0b11111111 >> zeroBits);
break;
}
}
do
{
rng.GetBytes(bytes);
// set most significant bits to 0 (because `value > max` if any of these bits is 1)
bytes[bytes.Length - 1] &= zeroBitsMask;
value = new BigInteger(bytes);
// `value > max` 50% of the times, in which case the fastest way to keep the distribution uniform is to try again
} while (value > max);
return value;
}
using (var rng = RandomNumberGenerator.Create())
{
BigInteger min = 0;
BigInteger max = 5;
var attempts = 10000000;
var count = new int[(int)max + 1];
var sw = Stopwatch.StartNew();
for (var i = 0; i < attempts; i++)
{
var v = BigIntegerUtils.RandomInRange(rng, min, max);
count[(int)v]++;
}
var time = sw.Elapsed;
Console.WriteLine("Generated {0} big integers from {1} to {2} in {3}", attempts, min, max, time);
Console.WriteLine("On average: {0} ms/integer or {1} integers/second", time.TotalMilliseconds / attempts, attempts / time.TotalSeconds);
for (var i = 0; i <= max; i++)
Console.WriteLine("{0} generated {1}% of the times ({2} times)", i, count[i] * 100d / attempts, count[i]);
}
Generated 10000000 big integers from 0 to 5 in 00:00:09.5413677
On average: 0.00095413677 ms/integer or 1048067.77334449 integers/second
0 generated 16.66633% of the times (1666633 times)
1 generated 16.6717% of the times (1667170 times)
2 generated 16.66373% of the times (1666373 times)
3 generated 16.6666% of the times (1666660 times)
4 generated 16.68271% of the times (1668271 times)
5 generated 16.64893% of the times (1664893 times)
Generated 10000000 big integers from 0 to 10^100 in 00:00:17.5036570
On average: 0.0017503657 ms/integer or 571309.184132207 integers/second
这是该类的NextBigInteger扩展方法Random。它基于出色的 Fabio Iotti实现，为了简洁而进行了修改。
/// <summary>
/// Returns a random BigInteger that is within a specified range.
/// The lower bound is inclusive, and the upper bound is exclusive.
/// </summary>
public static BigInteger NextBigInteger(this Random random,
BigInteger minValue, BigInteger maxValue)
{
if (minValue > maxValue) throw new ArgumentException();
if (minValue == maxValue) return minValue;
BigInteger zeroBasedUpperBound = maxValue - 1 - minValue; // Inclusive
Debug.Assert(zeroBasedUpperBound.Sign >= 0);
byte[] bytes = zeroBasedUpperBound.ToByteArray();
Debug.Assert(bytes.Length > 0);
Debug.Assert((bytes[bytes.Length - 1] & 0b10000000) == 0);
// Search for the most significant non-zero bit
byte lastByteMask = 0b11111111;
for (byte mask = 0b10000000; mask > 0; mask >>= 1, lastByteMask >>= 1)
{
if ((bytes[bytes.Length - 1] & mask) == mask) break; // We found it
}
while (true)
{
random.NextBytes(bytes);
bytes[bytes.Length - 1] &= lastByteMask;
var result = new BigInteger(bytes);
Debug.Assert(result.Sign >= 0);
if (result <= zeroBasedUpperBound) return result + minValue;
}
}
BigInteger为了返回理想范围内的值而被丢弃的实例百分比平均为 30%（最佳情况为 0%，最坏情况为 50%）。
随机数的分布是均匀的。
使用示例：
Random random = new();
BigInteger value = random.NextBigInteger(BigInteger.Zero, new BigInteger(1000));
注意：从 . 返回的字节结构有BigInteger.ToByteArray 据可查（在备注部分），因此可以相当安全地假设BigInteger. 的byte[]表示在未来版本的 .NET 平台中不会改变。如果发生这种情况，上述NextBigInteger实现可能会以令人讨厌的方式失败，例如进入无限循环或在错误范围内生成数字。我添加了一些调试断言，它们在当前表示中永远不会失败，但检查无效条件的覆盖范围绝不是彻底的。
这是在范围内生成数字而不丢弃值并允许 BigIntegers 用于最小值和最大值的另一种方法。
public BigInteger RandomBigInteger(BigInteger min, BigInteger max)
{
Random rnd = new Random();
string numeratorString, denominatorString;
double fraction = rnd.NextDouble();
BigInteger inRange;
//Maintain all 17 digits of precision,
//but remove the leading zero and the decimal point;
numeratorString = fraction.ToString("G17").Remove(0, 2);
//Use the length instead of 17 in case the random
//fraction ends with one or more zeros
denominatorString = string.Format("1E{0}", numeratorString.Length);
inRange = (max - min) * BigInteger.Parse(numeratorString) /
BigInteger.Parse(denominatorString,
System.Globalization.NumberStyles.AllowExponent)
+ min;
return inRange;
}
为了一般性，您可能还想指定精度。这似乎有效。
public BigInteger RandomBigIntegerInRange(BigInteger min, BigInteger max, int precision)
{
Random rnd = new Random();
string numeratorString, denominatorString;
double fraction = rnd.NextDouble();
BigInteger inRange;
numeratorString = GenerateNumeratorWithSpecifiedPrecision(precision);
denominatorString = string.Format("1E{0}", numeratorString.Length);
inRange = (max - min) * BigInteger.Parse(numeratorString) / BigInteger.Parse(denominatorString, System.Globalization.NumberStyles.AllowExponent) + min;
return inRange;
}
private string GenerateNumeratorWithSpecifiedPrecision(int precision)
{
Random rnd = new Random();
string answer = string.Empty;
while(answer.Length < precision)
{
answer += rnd.NextDouble().ToString("G17").Remove(0, 2);
}
if (answer.Length > precision) //Most likely
{
answer = answer.Substring(0, precision);
}
return answer;
}
以下Range方法将IEnumerable<BigInteger>在您指定的范围内返回一个。一个简单的扩展方法将在 IEnumerable 中返回一个随机元素。
public static IEnumerable<BigInteger> Range(BigInteger from, BigInteger to)
{
for(BigInteger i = from; i < to; i++) yield return i;
}
public static class Extensions
{
public static BigInteger RandomElement(this IEnumerable<BigInteger> enumerable, Random rand)
{
int index = rand.Next(0, enumerable.Count());
return enumerable.ElementAt(index);
}
}
用法：
Random rnd = new Random();
var big = Range(new BigInteger(10000000000000000), new BigInteger(10000000000000020)).RandomElement(rnd);
// 返回随机值，在本例中为 10000000000000003