考虑这个有效的方法：
public static bool mightBePrime(int N) {
BigInteger a = rGen.Next (1, N-1);
return modExp (a, N - 1, N) == 1;
}
现在，为了满足我所学班级的要求，mightBePrime 必须接受一个 BigInteger N，但这意味着我需要一种不同的方式来生成我的随机 BigInteger a。
我的第一个想法是做类似于 BigInteger a = (N-1) * rGen.NextDouble () 的事情，但是一个 BigInteger 不能乘以一个 double。
我该如何生成一个介于 1 和 N-1 之间的随机 BigInteger，其中 N 是一个 BigInteger？
保罗在评论中建议我使用随机字节生成数字，如果数字太大，则将其丢弃。以下是我的解决方案（结合了马塞尔的答案和保罗的建议）：
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/ 对此有所帮助。
do-while 循环会使代码更加DRY。 - svickbytes [bytes.Length-1]&=（byte）0x7F;。如果您这样做，就不需要额外的字节了。 - svick if (bytes[highestByteIndex] > highestByte) {
bytes[highestByteIndex] = (Byte)_Random.Next(highestByte + 1);
}只有当数字仍然太大时，才循环并重新计算整个数字。 - Christophpublic BigInteger getRandom(int length){
Random random = new Random();
byte[] data = new byte[length];
random.NextBytes(data);
return new BigInteger(data);
}
return new BigInteger(data)？ - spendera 到 b 之间的数字，而这个函数返回了 x。那么你只需要 a + x.Abs().Mod(b - a)。在 C# 的 BigInteger 实现中是可能的。 - pkuderovBigInteger之前平均会失败64次。min和max之间的随机BigInteger。min>max，则交换min和max
2.为了简化实现，我们将范围从[min，max]移动到[0，max-min]，这样我们就不必处理符号位。max包含多少个字节（bytes.Length）zeroBits）bytes.Length字节zeroBits位必须为0，因此我们使用zeroBitMask通过在最高有效字节上进行单个比特与比特&操作来设置它们，这将通过减少生成超出我们范围的数字的机会来节省大量时间。> max，如果是，则重试。min添加到我们的结果中，将范围从[0，max-min]解除移动到[min，max]。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
这是一个针对Random类的NextBigInteger扩展方法，与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;
}
对于我的使用情况，我做了以下操作：
Random rnd = new Random();
BigInteger myVal = rnd.NextBigInteger(50,100); //returns a 50-99 bit BigInteger
代码：
/// <summary>
/// Returns a random BigInteger with a minimum bit count between <paramref name="minBitLength"/>(inclusive) and <paramref name="maxBitLength"/>(exclusive).
/// </summary>
/// <param name="minBitLength">The inclusive lower bit length of the random BigInteger returned.</param>
/// <param name="maxBitLength">The exclusive upper bit length of the random BigInteger returned. <paramref name="maxBitLength"/> must be greater than or equal to minValue.</param>
public static BigInteger NextBigInteger(this Random rnd, int minBitLength, int maxBitLength)
{
if (minBitLength < 0) throw new ArgumentOutOfRangeException();
int bits = rnd.Next(minBitLength, maxBitLength);
if (bits == 0) return BigInteger.Zero;
byte[] bytes = new byte[(bits + 7) / 8];
rnd.NextBytes(bytes);
// For the top byte, place a leading 1-bit then downshift to achieve desired length.
bytes[^1] = (byte)((0x80 | bytes[^1]) >> (7 - (bits - 1) % 8));
return new BigInteger(bytes, true);
}
示例结果：
____Example Lengths___ ___Example Results___
NextBigInteger(0,0) ==> 0 0 0 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0
NextBigInteger(0,1) ==> 0 0 0 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0
NextBigInteger(0,2) ==> 1 1 1 0 1 0 0 1 0 0 1 | 1 1 1 1 0 1 0
NextBigInteger(0,3) ==> 2 2 2 1 2 0 0 0 1 0 2 | 0 1 0 2 0 1 2
NextBigInteger(0,4) ==> 3 2 0 3 0 0 0 3 1 3 3 | 0 1 1 0 3 1 0
NextBigInteger(0,5) ==> 1 4 1 2 4 1 2 0 3 1 2 | 1 1 10 10 14 11 8
NextBigInteger(0,6) ==> 3 5 1 1 5 5 3 5 1 4 3 | 0 0 1 3 2 7 27
NextBigInteger(1,1) ==> 1 1 1 1 1 1 1 1 1 1 1 | 1 1 1 1 1 1 1
NextBigInteger(1,2) ==> 1 1 1 1 1 1 1 1 1 1 1 | 1 1 1 1 1 1 1
NextBigInteger(1,3) ==> 2 1 2 1 2 2 2 2 1 1 1 | 1 1 1 1 2 2 3
NextBigInteger(1,4) ==> 1 2 3 3 2 1 1 2 2 2 1 | 7 3 1 1 6 1 5
NextBigInteger(1,5) ==> 4 3 1 2 3 1 4 4 1 1 3 | 1 3 1 6 6 12 7
NextBigInteger(1,6) ==> 5 5 4 1 1 2 3 2 1 1 1 | 1 28 7 5 25 15 13
NextBigInteger(2,2) ==> 2 2 2 2 2 2 2 2 2 2 2 | 2 2 3 2 3 2 3
NextBigInteger(2,3) ==> 2 2 2 2 2 2 2 2 2 2 2 | 2 2 3 2 2 3 3
NextBigInteger(2,4) ==> 3 3 2 3 3 3 3 3 3 2 3 | 3 2 7 6 3 3 3
NextBigInteger(2,5) ==> 2 4 2 2 4 4 2 2 4 3 2 | 6 3 13 2 6 4 11
NextBigInteger(2,6) ==> 5 3 5 3 2 3 2 4 4 5 3 | 2 3 17 2 27 14 18
NextBigInteger(3,3) ==> 3 3 3 3 3 3 3 3 3 3 3 | 4 4 5 7 6 7 4
NextBigInteger(3,4) ==> 3 3 3 3 3 3 3 3 3 3 3 | 6 5 4 7 6 4 6
NextBigInteger(3,5) ==> 3 3 3 3 4 4 4 4 3 4 4 | 6 10 12 6 6 15 7
NextBigInteger(3,6) ==> 4 4 3 3 3 4 3 5 4 3 4 | 28 22 5 11 25 8 6
NextBigInteger(4,4) ==> 4 4 4 4 4 4 4 4 4 4 4 | 12 8 8 9 8 10 13
NextBigInteger(4,5) ==> 4 4 4 4 4 4 4 4 4 4 4 | 15 10 10 8 14 8 13
NextBigInteger(4,6) ==> 5 5 5 5 4 5 5 4 5 5 5 | 15 13 14 31 19 15 21
Random.Next() 隐式处理了一些范围检查。BigInteger，而不是在特定数值范围内生成随机数，这也是问题所问的。 - Theodor ZouliasRange方法将返回您指定范围内的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
Range仅允许整数参数。2）即使Range允许使用BigInteger，它也会返回范围内所有值的序列，按顺序排列。他想要在从<=值<到的范围内获得一个随机数。 - Jim Mischel
System.Random。 - Michael Liu