Случайное простое число

В криптографии под случайным простым числом понимается простое число, содержащее в двоичной записи заданное количество битов <math>k</math>, на алгоритм генерации которого накладываются определенные ограничения. Получение случайных простых чисел является неотъемлемой частью процедур выработки ключей во многих криптографических алгоритмах, включая RSA и ElGamal.

Ввиду того, что тестирование простоты больших чисел требует существенных временных затрат, требование простоты получаемого числа часто ослабляют до сильной псевдопростоты по нескольким различным случайным основаниям. Существующие алгоритмы тестирования сильной псевдопростоты на порядки быстрее лучших известных алгоритмов тестирования простоты. В то же время, числа, успешно прошедшие тестирования сильной псевдопростоты по нескольким случайным основаниям, с большой вероятностью являются простыми, причем эта вероятность растет с ростом количества оснований, по которым проводится тестирование.

Требования к алгоритму и его реализации

Требования к алгоритмам генерации случайных простых чисел сводятся к следующим двум:

• Распределение получаемых простых чисел должно быть близко к равномерному на множестве всех k-битных простых чисел. Существует несколько способов обеспечить выполнимость этого требования.
• Процесс генерации конкретного случайного простого числа нельзя воспроизвести, даже зная детали алгоритма и его реализации. Обычно выполнение этого требования обеспечивается использованием криптостойкого ГПСЧ, проинициализированного некоторым ключом, получаемым извне (т. е. не являющимся частью алгоритма или его реализации). В качестве ключа может выступать, например, значение криптографической хеш-функции от секретной фразы, запрашиваемой у пользователя.

Типовые алгоритмы генерации случайных простых чисел

Везде далее предполагается использование криптографически стойкого ГПСЧ, проинициализированного с помощью секретного ключа (детали зависят от используемого ГПСЧ и способа получения и представления ключа).

Тестирование простоты

Проверить (вероятную) простоту числа p, содержащего k битов, можно так:

1. Убедиться, что p не делится на небольшие простые числа 3, 5, 7, 11, и т.д. до некоторого небольшого предела (например, 256). Такая проверка позволяет эффективно отсечь множество заведомо составных чисел, прежде чем проверять их посредством более трудоёмких алгоритмов. Так, проверка делимости p на простые числа 2, 3, 5 и 7 отсеивает все четные числа и 54% нечетных чисел, проверка делимости p на все простые числа до 100 отсеивает 76% нечетных чисел, а проверка делимости p на все простые числа до 256 отсеивает 80% нечетных чисел.
2. Выполнить тест Миллера — Рабина с количеством раундов не меньше k.

Если число p не проходит хотя бы одной проверки — оно не является простым. В противном случае с большой вероятностью (зависящей от количества раундов) число p является простым.

Прямое построение

1. Сгенерировать <math>k-1</math> случайных битов и составить из них k-битное число p со старшим битом равным 1.
2. Увеличить p на 1 и проверить его простоту. Повторять этот шаг до тех пор, пока не будет найдено простое число.

Второй шаг можно ускорить, если рассматривать только нечетные числа или числа сравнимые с 1 и 5 по модулю 6 и т.п.

(n—1)-методы

(n—1)-методы построения простых чисел используют знание о простых делителях числа n—1 для тестирования простоты n с помощью теста простоты Люка.

Типичный представитель этого класса методов описан в книге «Введение в криптографию» под редакцией В. В. Ященко.

Генерация простых чисел Софи Жермен

Простые числа Софи Жермен — такие простые p, что 2p + 1 тоже простое.

Отрывок, характеризующий Случайное простое число

– Но вот что, по правде вам сказать, ma tante…
– Что, что, мой друг; пойдем вот тут сядем.
Николай вдруг почувствовал желание и необходимость рассказать все свои задушевные мысли (такие, которые и не рассказал бы матери, сестре, другу) этой почти чужой женщине. Николаю потом, когда он вспоминал об этом порыве ничем не вызванной, необъяснимой откровенности, которая имела, однако, для него очень важные последствия, казалось (как это и кажется всегда людям), что так, глупый стих нашел; а между тем этот порыв откровенности, вместе с другими мелкими событиями, имел для него и для всей семьи огромные последствия.
– Вот что, ma tante. Maman меня давно женить хочет на богатой, но мне мысль одна эта противна, жениться из за денег.
– О да, понимаю, – сказала губернаторша.
– Но княжна Болконская, это другое дело; во первых, я вам правду скажу, она мне очень нравится, она по сердцу мне, и потом, после того как я ее встретил в таком положении, так странно, мне часто в голову приходило что это судьба. Особенно подумайте: maman давно об этом думала, но прежде мне ее не случалось встречать, как то все так случалось: не встречались. И во время, когда Наташа была невестой ее брата, ведь тогда мне бы нельзя было думать жениться на ней. Надо же, чтобы я ее встретил именно тогда, когда Наташина свадьба расстроилась, ну и потом всё… Да, вот что. Я никому не говорил этого и не скажу. А вам только.
Губернаторша пожала его благодарно за локоть.
– Вы знаете Софи, кузину? Я люблю ее, я обещал жениться и женюсь на ней… Поэтому вы видите, что про это не может быть и речи, – нескладно и краснея говорил Николай.
– Mon cher, mon cher, как же ты судишь? Да ведь у Софи ничего нет, а ты сам говорил, что дела твоего папа очень плохи. А твоя maman? Это убьет ее, раз. Потом Софи, ежели она девушка с сердцем, какая жизнь для нее будет? Мать в отчаянии, дела расстроены… Нет, mon cher, ты и Софи должны понять это.
Николай молчал. Ему приятно было слышать эти выводы.
– Все таки, ma tante, этого не может быть, – со вздохом сказал он, помолчав немного. – Да пойдет ли еще за меня княжна? и опять, она теперь в трауре. Разве можно об этом думать?
– Да разве ты думаешь, что я тебя сейчас и женю. Il y a maniere et maniere, [На все есть манера.] – сказала губернаторша.
– Какая вы сваха, ma tante… – сказал Nicolas, целуя ее пухлую ручку.


Приехав в Москву после своей встречи с Ростовым, княжна Марья нашла там своего племянника с гувернером и письмо от князя Андрея, который предписывал им их маршрут в Воронеж, к тетушке Мальвинцевой. Заботы о переезде, беспокойство о брате, устройство жизни в новом доме, новые лица, воспитание племянника – все это заглушило в душе княжны Марьи то чувство как будто искушения, которое мучило ее во время болезни и после кончины ее отца и в особенности после встречи с Ростовым. Она была печальна. Впечатление потери отца, соединявшееся в ее душе с погибелью России, теперь, после месяца, прошедшего с тех пор в условиях покойной жизни, все сильнее и сильнее чувствовалось ей. Она была тревожна: мысль об опасностях, которым подвергался ее брат – единственный близкий человек, оставшийся у нее, мучила ее беспрестанно. Она была озабочена воспитанием племянника, для которого она чувствовала себя постоянно неспособной; но в глубине души ее было согласие с самой собою, вытекавшее из сознания того, что она задавила в себе поднявшиеся было, связанные с появлением Ростова, личные мечтания и надежды.
Когда на другой день после своего вечера губернаторша приехала к Мальвинцевой и, переговорив с теткой о своих планах (сделав оговорку о том, что, хотя при теперешних обстоятельствах нельзя и думать о формальном сватовстве, все таки можно свести молодых людей, дать им узнать друг друга), и когда, получив одобрение тетки, губернаторша при княжне Марье заговорила о Ростове, хваля его и рассказывая, как он покраснел при упоминании о княжне, – княжна Марья испытала не радостное, но болезненное чувство: внутреннее согласие ее не существовало более, и опять поднялись желания, сомнения, упреки и надежды.
В те два дня, которые прошли со времени этого известия и до посещения Ростова, княжна Марья не переставая думала о том, как ей должно держать себя в отношении Ростова. То она решала, что она не выйдет в гостиную, когда он приедет к тетке, что ей, в ее глубоком трауре, неприлично принимать гостей; то она думала, что это будет грубо после того, что он сделал для нее; то ей приходило в голову, что ее тетка и губернаторша имеют какие то виды на нее и Ростова (их взгляды и слова иногда, казалось, подтверждали это предположение); то она говорила себе, что только она с своей порочностью могла думать это про них: не могли они не помнить, что в ее положении, когда еще она не сняла плерезы, такое сватовство было бы оскорбительно и ей, и памяти ее отца. Предполагая, что она выйдет к нему, княжна Марья придумывала те слова, которые он скажет ей и которые она скажет ему; и то слова эти казались ей незаслуженно холодными, то имеющими слишком большое значение. Больше же всего она при свидании с ним боялась за смущение, которое, она чувствовала, должно было овладеть ею и выдать ее, как скоро она его увидит.