Простое число
- 1 year ago
- 0
- 0
В криптографии под случайным простым числом понимается простое число , содержащее в двоичной записи заданное количество битов , на алгоритм генерации которого накладываются определенные ограничения. Получение случайных простых чисел является неотъемлемой частью процедур выработки ключей во многих криптографических алгоритмах, включая RSA и ElGamal .
Ввиду того, что тестирование простоты больших чисел требует существенных временных затрат, требование простоты получаемого числа часто ослабляют до сильной псевдопростоты по нескольким различным случайным основаниям. Существующие алгоритмы тестирования сильной псевдопростоты на порядки быстрее лучших известных алгоритмов тестирования простоты. В то же время, числа, успешно прошедшие тестирования сильной псевдопростоты по нескольким случайным основаниям, с большой вероятностью являются простыми, причём эта вероятность растет с ростом количества оснований, по которым проводится тестирование.
Требования к алгоритмам генерации случайных простых чисел сводятся к следующим двум:
Везде далее предполагается использование криптографически стойкого ГПСЧ , проинициализированного с помощью секретного ключа (детали зависят от используемого ГПСЧ и способа получения и представления ключа).
Проверить (вероятную) простоту числа p , содержащего k битов, можно так:
Если число p не проходит хотя бы одной проверки — оно не является простым. В противном случае с большой вероятностью (зависящей от количества раундов) число p является простым.
Второй шаг можно ускорить, если рассматривать только нечетные числа или числа, сравнимые с 1 и 5 по модулю 6 и т. п.
( n —1)-методы построения простых чисел используют знание о простых делителях числа n —1 для тестирования простоты n с помощью теста простоты Люка .
Типичный представитель этого класса методов описан в книге «Введение в криптографию» под редакцией В. В. Ященко.
Простые числа Софи Жермен — такие простые p, что 2p + 1 тоже простое.