Ответ 1

Пол предложил в комментарии, что я генерирую число, используя случайные байты, а затем выбросьте его, если он слишком большой. Вот что я придумал (Марсель отвечает + совет Павла):

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/ тоже помог.

Ответ 2

Используйте случайный класс

public BigInteger getRandom(int length){
    Random random = new Random();
    byte[] data = new byte[length];
    random.NextBytes(data);
    return new BigInteger(data);
}

Ответ 3

Наивная реализация не будет работать в среднем 64 раза, прежде чем найти допустимый BigInteger в пределах указанного диапазона.

В худшем случае моя реализация будет повторять в среднем только 0,5 раза (читайте так: 50% времени, когда он найдет результат с первой попытки).

Кроме того, в отличие от модульной арифметики, моя реализация поддерживает равномерное распределение.

Объяснение

Мы должны создать случайный BigInteger между min и max.

• Если min > max, мы поменяем min на max
• Чтобы упростить реализацию, мы смещаем наш диапазон от [min, max] до [0, max-min], поэтому нам не придется иметь дело со знаковым битом
• Мы подсчитываем, сколько байтов max содержит (bytes.Length)
• Из самого значащего бита мы подсчитываем, сколько бит равно 0 (zeroBits)
• Мы генерируем случайную последовательность из bytes.Length bytes
• Мы знаем, что для нашей последовательности < max не менее zeroBits битов из самого значимого бита должно быть 0, поэтому мы используем 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]);
}

Тест-выход на моем 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

Ответ 4

Создать массив байтов и преобразовать в 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 слишком мал, то случайное генерирует одно и то же значение. Таким образом, вы можете установить случайное значение вне функции:

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...
}

Ответ 5

Здесь альтернативный способ генерации чисел в пределах диапазона, не выбрасывая значения и позволяя BigIntegers для min и max.

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;
    } 

Ответ 6

Следующий 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