如何在一定范围内生成随机BigInteger？
考虑一下运行良好的方法：
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？
Paul在评论中建议我使用随机字节生成一个数字，如果它太大则扔掉它。 这就是我想出的结果（Marcel的回答+ 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％）。
此外，与模块化算术不同，我的实现保持均匀分布 。
说明
我们必须在min和max之间生成一个随机的BigInteger 。
- 如果
min > max，我们将min与max交换 - 为了简化实现，我们将范围从
[min, max]移到[0, max-min]，这样我们就不必处理符号位了 - 我们计算
max包含的字节数（bytes.Length） - 从最重要的位，我们计算多少位是0（
zeroBits） - 我们生成一个随机的
bytes.Length字节序列 - 我们知道，对于我们的序列为
< max， 最高有效位的至少0 位必须为0，所以我们使用zeroBitMask在最高有效字节上通过单个位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]); }
在i7-6500U上测试输出：
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)
我的i7-6500U的另一个测试输出
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
创建字节数组并转换为BigInteger：
public BigInteger random_generate(BigInteger maxValue) { Random random = new Random(); byte[] maxValue_array = maxValue.ToByteArray(); byte[] randomValue_array = new byte[maxValue_array.Count()]; bool on_limit = true; //make sure randomValue won't greater than maxValue for (int generate_byte = maxValue_array.Count() - 1; generate_byte >= 0; generate_byte--) { byte random_byte = 0; if (on_limit) { random_byte = (byte)random.Next(maxValue_array[generate_byte]); if (random_byte != (byte)random.Next(maxValue_array[generate_byte])) { on_limit = false; } } else { random_byte = (byte)random.Next(256); } randomValue_array[generate_byte] = random_byte; } return new BigInteger(randomValue_array); }
如果maxValue太小，则random会生成相同的值。 所以你可以在函数外面设置随机：
static void Main(string[] args) { Random random = new Random(); BigInteger i = random_generate(10, random); //10 is just a example } public BigInteger random_generate(BigInteger maxValue, Random random) { byte[] maxValue_array = maxValue.ToByteArray(); //...rest of the code... }
这是另一种在范围内生成数字而不丢弃值并允许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 。 一个简单的Extension方法将返回IEnumerable中的随机元素。
public static IEnumerable 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 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