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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 67
Итак, p = 43, g = 3, t = 15. Определим (
0
, b
0
, x
0
) = (0, 0, 1), и будем строить
две последовательности (a
i
, b
i
, x
i
) и (a
2i
, b
2i
, x
2i
) по формулам (2.27) и (2.28):
i a
i
b
i
x
i
a
2i
b
2i
x
2i
1 2 0 10 6 0 11
2 3 0 21 7 1 22
3 6 0 11 15 2 36
4 7 0 36 30 6 11
5 7 1 22 31 7 22
На 5-м шаге значения x
i
и x
2i
совпали. Составим уравнение (2.30):
x(31−7)+y(43−1) ≡ 1−7 ( mod 42), или, 24x+42y ≡ 36 ( mod 42).
Вычислим Н.О.Д.(a
j
− a
i
, p − 1) =Н.О.Д.(24, 42) = 6 6= 1.
Поделим все коэффициенты уравнения на 6:
4x + 7y ≡ 6 ( mod 42).
С помощью расширенного алгоритма Евклида (см. разд 1.8) решим
уравнение 4x + 7y = 1, подставляя вместо A и B коэффициенты этого
уравнения (поменяв их местами, чтобы A было больше B ):
A B A mod B A div B y x
7 4 3 1 -1 2
4 3 1 1 1 -1
3 1 0 3 0 1
Таким образом, 7 ·(−1) + 4 ·2 = 1, или, 7 ·(−6) + 4 ·12 = 6. Положим,
x
0
= x = 12. Поскольку, d > 1, то корень X уравнения (2.32) определяется
с точностью до слагаемое (p − 1)/d = 7, т.е. имеет вид X = x
0
+ 7k , где
k ∈ Z. Будем подставлять в (2.32) последовательно числа 12, 19, 25, ..., пока
не получим тождество 3
25
mod 43 = 15. Задача решена.
Глава 2. Простые алгоритмы факторизации                                              67

Итак, p = 43, g = 3, t = 15. Определим (0 , b0 , x0 ) = (0, 0, 1), и будем строить
две последовательности (ai , bi , xi ) и (a2i , b2i , x2i ) по формулам (2.27) и (2.28):

         i   ai bi xi a2i b2i x2i
         1   2   0 10      6    0   11
         2   3   0 21      7    1   22
         3   6   0 11 15        2   36
         4   7   0 36 30        6   11
         5   7   1 22 31        7   22

       На 5-м шаге значения xi и x2i совпали. Составим уравнение (2.30):

x(31−7)+y(43−1) ≡ 1−7 ( mod 42),                 или, 24x+42y ≡ 36 ( mod 42).

       Вычислим Н.О.Д.(aj − ai , p − 1) =Н.О.Д.(24, 42) = 6 6= 1.
       Поделим все коэффициенты уравнения на 6:

  4x + 7y ≡ 6 ( mod 42).

       С помощью расширенного алгоритма Евклида (см. разд 1.8) решим
уравнение 4x + 7y = 1, подставляя вместо A и B коэффициенты этого
уравнения (поменяв их местами, чтобы A было больше B ):

        A B A mod B A div B y                x
        7    4      3           1        -1 2
        4    3      1           1        1 -1
        3    1      0           3        0   1
       Таким образом, 7 · (−1) + 4 · 2 = 1, или, 7 · (−6) + 4 · 12 = 6. Положим,
x0 = x = 12. Поскольку, d > 1, то корень X уравнения (2.32) определяется
с точностью до слагаемое (p − 1)/d = 7, т.е. имеет вид X = x0 + 7k , где
k ∈ Z. Будем подставлять в (2.32) последовательно числа 12, 19, 25, ..., пока
не получим тождество 325 mod 43 = 15. Задача решена.

Страницы