C# генератор случайных чисел BigInt

Question

C# генератор случайных чисел BigInt

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

Выберите" p", простое число с L битами, где 512

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

774 1

c#biginteger dsa

1 ответ:

Comments

Ничего не найдено.

dtb · Accepted Answer · 2010-06-03 15:22:43

Вы можете сгенерировать случайное число с битами n, используя следующий код:
var rng = new RNGCryptoServiceProvider();
byte[] bytes = new byte[n / 8];
rng.GetBytes(bytes);

BigInteger p = new BigInteger(bytes);
Результат, конечно, случайный и не обязательно простой.
КлассBigInteger был введен в .NET 4.0 Framework.

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

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

Таким образом, вы могли бы сделать что-то вроде этого:
var p = Enumerable.Range(0, numberOfCandidates)
                  .Select(i => RandomOddNumber(bits))
                  .Where(x => !primesLessThan65000.Contains(x))
                  .Where(x => PrimalityTest(x))
                  .FirstOrDefault();