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

Глава 1. Простые числа                                                       15

      Из теоремы Ферма сразу следует, что если для некоторого a < p
выполнено условие ap−1 6≡ 1 ( mod p), тогда число p является составным.
Однако обращение малой теоремы Ферма не верно – существуют составные
числа p, для которых выполняется условие Ферма для каждого a, не
сравнимого с p. Такие числа называются числами Кармайкла и будут
рассмотрены в разделе 1.19.
      Следующая теорема дает критерий проверки простоты числа p и
одновременно примитивности корня a:

Теорема 1.3. (Критерий        примитивности         и   простоты).   Если   для
некоторых a и p выполнены условия:

   1. ap−1 ≡ 1( mod p),
   2. a(p−1)/q 6≡ 1( mod p) для ∀q|(p − 1),

тогда число p–простое, и a является примитивным корнем поля GFp (т.е.
генератором группы по умножению поля GFp ).

Пример. n = 1 022 333 835 329 657, n − 1 = 2 · 2957 · 146 063 · 292 877.

       3n−1 ≡ 1( mod n),
       3(n−1)/2 ≡ −1 ( mod n),
       3(n−1)/2597 ≡ 324224767363906 ( mod n),
       3(n−1)/146 063 ≡ 697302646321792 ( mod n),
       3(n−1)/292 877 ≡ 736785752408036 ( mod n).

      Поэтому число n в нашем примере является простым, а 3 является
примитивным корнем поля Галуа GFn .
      Отметим, что разбиение n − 1 в произведение простых сомножителей
само является очень сложной задачей, поэтому для длинных чисел этот
критерий простоты неприменим.


1.4. Метод пробных делений
      Метод пробных делений (the trial division) является наиболее простым
методом проверки простоты входного составного числа n или нахождения