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

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

47
Теорема 1.10. (о делителях чисел Ферма (Эйлер-Лука)). Пусть F
n
= 2
2
n
+
1, n ≥ 1, и p–простой делитель F
n
, тогда p ≡ 1 (mod 2
n+2
).
Доказательство. Пусть r–простой делитель F
n
, и пусть h–
наименьшее натуральное число такое, что 2
h
≡ 1 (mod r ). Т.к.
2
2
n
≡ 1(mod r ), то h = 2
n+1
. Далее, поскольку по малой теореме
Ферма 2
r−1
≡ 1(mod r ), то h является делителем r − 1. Т.к. n ≥ 2, то
r ≡ 1 ( mod 8). Из последнего условия следует (см.cтр.25), что 2 является
квадратичным вычетом по модулю r, откуда, 2
(r−1)/2
≡ −1(modr), что
влечет утверждение теоремы.
Пример. Рассмотрим F
5
= 2
32
+ 1. Любой его делитель по теореме
должен иметь вид 1 + 128k . И действительно, F
5
= 4 294 967 297 = 641 ·
6 700 417 = (1 + 5 · 128) · (1 + 52347 ·128).
Сведения о последних разложениях чисел Ферма можно найти на сайте
([28]): http://www.prothsearch.net/fermat.html
Ниже мы выпишем таблицу разложений первых чисел Ферма:
F
0
= 3
F
1
= 5
F
2
= 17
F
3
= 257
F
4
= 65537
F
5
= 641 · 6700417
F
6
= 274177 · 67280421310721
F
7
= 59649589127497217 · 5704689200685129054721
F
8
= 1238926361552897 · P 62
F
9
= 2424833 · 7455602825647884208337395736200454918783366342657 · P 99
F
10
= 45592577 · 6487031809 · 4659775785220018543264560743076778192897·
·P 252
F
11
= 319489 · 974849 · 167988556341760475137 · 3560841906445833920513·
·P 564
Здесь запись P k с индексом k , например P 564, обозначает известное простое
число длины k в десятичной записи.
                                                                          47

                                                                         n
Теорема 1.10. (о делителях чисел Ферма (Эйлер-Лука)). Пусть Fn = 22 +
1, n ≥ 1, и p–простой делитель Fn , тогда p ≡ 1 (mod 2n+2 ).

       Доказательство. Пусть r –простой делитель Fn , и пусть h–
наименьшее натуральное число такое, что          2h   ≡    1 (mod r ). Т.к.
  n
22    ≡    1(mod r ), то h = 2n+1 . Далее, поскольку по малой теореме
Ферма 2r−1 ≡ 1(mod r ), то h является делителем r − 1. Т.к. n ≥ 2, то
r ≡ 1 ( mod 8). Из последнего условия следует (см.cтр.25), что 2 является
квадратичным вычетом по модулю r , откуда, 2(r−1)/2 ≡ −1(modr), что
влечет утверждение теоремы.

       Пример. Рассмотрим F5 = 232 + 1. Любой его делитель по теореме
должен иметь вид 1 + 128k . И действительно, F5 = 4 294 967 297 = 641 ·
6 700 417 = (1 + 5 · 128) · (1 + 52347 · 128).

       Сведения о последних разложениях чисел Ферма можно найти на сайте
([28]): http://www.prothsearch.net/fermat.html
       Ниже мы выпишем таблицу разложений первых чисел Ферма:
 F0 = 3
 F1 = 5
 F2 = 17
 F3 = 257
 F4 = 65537
F5 = 641 · 6700417
F6 = 274177 · 67280421310721
F7 = 59649589127497217 · 5704689200685129054721
F8 = 1238926361552897 · P 62
F9 = 2424833 · 7455602825647884208337395736200454918783366342657 · P 99
F10 = 45592577 · 6487031809 · 4659775785220018543264560743076778192897·
      ·P 252
F11 = 319489 · 974849 · 167988556341760475137 · 3560841906445833920513·
      ·P 564
Здесь запись P k с индексом k , например P 564, обозначает известное простое
число длины k в десятичной записи.

Страницы