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

                                                                                      20

     Действительно, в этом случае, любой нетривиальный делитель 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,
        √
меньше b nc = 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 6= ±1 ( mod n),

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


1.7. Генерация простых чисел
         Во многих задачах теории чисел и криптографии возникает
необходимость генерации простых чисел заданного размера. Одним из
хороших способов порождения простых чисел является способ получения
простых чисел с помощью какой-нибудь формулы. Например, еще Л.Эйлер
предложил многочлен

                     p(x) = x2 + x + 41,

значения которого в первых 40 членах натурального ряда дают простые
числа.