Подтвердить что ты не робот

С# Случайный генератор BigInt

Я собираюсь реализовать алгоритм DSA, но есть проблема:

выберите "p", простое число с L битами, где 512 <= L <= 1024 и L кратно 64

Как я могу реализовать случайный генератор этого числа? Int64 имеет "только" длину 63 бит.

Ответ 1

Вы можете создать случайное число с битами n, используя этот код:

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

BigInteger p = new BigInteger(bytes);

Результат, конечно, случайный и не обязательно простой.

класс BigInteger был представлен в платформе .NET 4.0.

Для генерации больших простых чисел Википедия говорит:

Для больших простых чисел, используемых в криптографии, обычно используется модифицированная форма просеивания: произвольно выбранный диапазон нечетных чисел желаемого размера просеивается по ряду относительно малых нечетных простых чисел (обычно все простые числа меньше, чем 65000). Оставшиеся простые простые числа тестируются в случайном порядке с помощью стандартного теста прочности, такого как тест примитивности Миллера-Рабина для вероятных простых чисел.

Итак, вы можете сделать что-то вроде этого:

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