Математические основы защиты информации. Ишмухаметов Ш.Т - 32 стр.

                                                                                    33

     Действительно, в этом случае, любой нетривиальный делитель p числа
                      √
n должен быть больше n, что невозможно.

      Пример. Пусть n = 618 970 019 642 690 137 449 462 111. Число n − 1
имеет полное разложение вида

       n − 1 = 2 · 3 · 5 · 17 · 23 · 89 · 353 · 397 · 683 · 2113 · 2 931 542 417.

     Отметим, что наибольший делитель n − 1, равный 2 931 542 417,
        √
меньше ⌊ n⌋ = 24 879 108 095 803.
      Базис a = 2 не подходит по условию теоремы, т.к. 2(n−1)/q ≡ 1 ( mod
n) для всех делителей q . Выполним тест с базой a = 3:

m = 3(n−1)/p − 1 ≡ 180 591 065 836 317 083 554 066 745 ̸= ±1 ( mod n),

и, Н.О.Д.(n, m) = 1. Значит, возможные делители числа n имеют вид 1 + k ·
    √
p < n, откуда, 0 < k < 8486. Простым перебором всех k можно убедиться,
что n не имеет простых делителей, и, значит, является простым.
      Можно было также вместо выполнения делений применить теорему
для F , равного произведению трех наибольших делителей n − 1 (для них
                                        √
годится та же база a = 3), тогда F > ⌊ n⌋, откуда сразу следует, что
n–простое.


2.11. Генерация простых чисел
       Рассмотрим один способ генерации больших простых чисел,
основанный на тесте Поклингтона (стр.32) Пусть задано простое число
p:
      1. Выберем случайным образом чётное число R на промежутке p ≤
R ≤ 4p + 2 и определим n = pR + 1.
      2. Проверим число n на отсутствие малых простых делителей,
разделив его на малые простые числа.
      3. Выполним для числа n тест Миллера-Рабина (см.ниже на c.35) с
использованием нескольких различных баз a < p. Если при одном из тестов