82. Генерация большого простого числа и проверка его на простоту. Метод пробных делений

Если n – составное, то n = a ∙ b, где 1 < a  b причем . Поэтому для мы проверяем, делится ли n на d? Если делитель числа n не будет найден, то n – простое. В противном случае, будет найден минимальный простой делитель числа n, т.е. мы разложим n на два множителя.

Решето Эратосфена

Если мы хотим составить таблицу всех простых чисел среди чисел 2, 3, … , n, то нужно сначала вычеркнуть все числа, делящиеся на 2, кроме 2. Затем взять число 3 и вычеркнуть все последующие числа, делящиеся на 3. Затем взять следующее невычеркнутое число (т.е. 5) и вычеркнуть все последующие числа, делящиеся на него, и так далее. В итоге останутся лишь простые числа.

Для реализации метода нужен большой объем памяти ЭВМ, однако для составления таблиц простых чисел он является наилучшим.

Критерий Вильсона

Теорема 1.

Число n является простым тогда и только тогда, когда (n – 1)! + 1 делится на n.

Данный критерий иногда бывает удобен в доказательствах, но применять его для проверки простоты невозможно ввиду большой трудоемкости.

Тест Рабина–Миллера

1. Выбираем случайное число a из интервала [1; n–1] и проверяем с помощью алгоритма Евклида условие НОД (a, n) = 1.

2. Если оно не выполняется, то ответ “n – составное”.

3. Вычисляем z = a^t mod n.

4. Если z ≡ ±1 (mod n), то переходим к шагу 1.

5. Вычисляем mod n,  mod n, … ,  mod n до тех пор, пока не появится –1.

6. Если ни одно из этих чисел не равно –1, то ответ “n – составное”;

7. Если мы достигли n, то ответ неизвестен (и тест можно повторить еще раз).

83. Алгоритм эффективной реализации возведения целого числа в целую степень по модулю n.

84. Алгоритм схемы обмена ключами Диффи-Хеллмана.

Рассмотрим простейшую схему создания общего ключа двумя абонентами.

Абоненты выбирают большое простое число и – первообразный корень по модулю . Получается пара , которая объявляется открытой.

Абонент выбирает случайное большое секретное число и посылает абоненту : .

Абонент выбирает случайное большое секретное число и посылает абоненту : .

Абонент вычисляет ключ: .

Абонент вычисляет ключ: .

Пример

.

Возьмем, например . – открыта.

Абонент сгенерировал случайное число , и вычислив , послал абоненту .

Абонент сгенерировал случайное число , и вычислив , послал абоненту .

Абонент принял и вычислил ключ: .

Абонент принял и вычислил ключ: .

85. Алгоритм RSA.

86. Однонаправленная хэш-функция и её свойства.

87. Схемы безопасных хэш-функций.

88. Электронная цифровая подпись и её свойства.

Электро́нная по́дпись (ЭП) — реквизит электронного документа, позволяющий установить отсутствие искажения информации в электронном документе с момента формирования ЭП и проверить принадлежность подписи владельцу сертификата ключа ЭП.

свойства подписи:

 подпись аутентична, т.е. с ее помощью получателю документа можно доказать, что она принадлежит подписывающему;

 подпись служит доказательством, что только тот человек, чей автограф стоит на документе, мог подписать данный документ, и никто другой не смог бы этого сделать;

 подпись непереносима, т.е. является частью документа и поэтому перенести ее на другой документ невозможно;

 документ с подписью является неизменяемым, т.е. после подписания его невозможно изменить, оставив данный факт незамеченным;

 подпись неоспорима, т.е. человек, подписавший документ, в случае признания экспертизой, что именно он засвидетельствовал данный документ, не может оспорить факт подписания;

 любое лицо, имеющее образец подписи, может удостовериться в том, что данный документ подписан владельцем подписи.