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

                                                                          48

      Первым в последовательности чисел Ферма, которые еще не полностью
факторизованы на сегодняшний день, является F12 . Совсем недавно, в марте
2010 г. Майклом Вангом (Michael Vang) был найден шестой фактор F12 ,
равный

P6 = 17353230210429594579133099699123162989482444520899 · 215 +1.

      Интересно, что предыдущие делители F12 были найдены в 1877 г.,
1903 г. (два делителя), 1974 г. и 1986 г. соответственно. Однако, остался
еще один составной кофактор этого числа, состоящий из 1033 десятичных
цифр, который еще не разложен до конца.
      Есть частичные сведения также о числах Ферма с большими номерами,
некоторые из которых просто огромные! Например, Янг (J.Young) показал,
что число F 213319 имеет кофактор 3 · 2 213321 + 1.

Числа Мерсенна

     Числами Мерсенна называются числа вида Mp = 2p − 1 с простыми
индексами p. Начальная последовательность чисел Мерсенна имеет вид:

1, 3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147483647.

Теорема 1.11. (о делителях чисел Мерсенна). Пусть p ≥ 3–простое число,
q –делитель Mp = 2p − 1, тогда q ≡ 1 (mod 2p) и q ≡ ±1 (mod 8).

      Доказательство. По предположению, 2p ≡ 1 (mod q) и по малой
теореме Ферма, 2q−1 ≡ 1 (modq). Поэтому, порядок 2 (т.е. наименьший
показатель t такой, что 2t ≡ 1 (modq) обозначается ordq (2)) является
одновременно делителем p и q − 1. Он не может быть равен 1, поэтому он
равен p, откуда p|(q − 1), т.е. q = 1 + mp. Т.к. оба числа p и q –нечетные,
то m = 2k –четно, откуда q = 1 + 2kp. Значит, p–делитель (q − 1)/2. Т.к
2p ≡ 1 (mod q), то 2(q−1)/2 ≡ 1 (mod q), откуда символ Лежандра (2/q) = 1
и q ≡ ±1 (mod 8).

      Числа Мерсенна получили известность в связи с эффективным
критерием простоты Люка — Лемера, благодаря которому простые числа