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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4. Метод квадратичного решета 123
Учитывая, что s(y) ≡ 0 (mod 2
k
), поделим последнее уравнение на
2
k
:
f + r ≡ 0 (mod 2), где f = [s(y)/2
k
] (mod 2). (4.101)
Итак, получим искомое решение в виде z = y+2
k
·f , где f вычисляется
по формулам (4.101).
Выполним соответствующие расчеты для нашего примера для степени
k + 1 = 5 при y ∈ {2, 3}:
f = ((y
2
+ 807y − 214) mod 8)/4 = ((y
2
+ 7y − 6) mod 8)/4
1. y = 2, f = ((4 + 14 − 6) mod 8)/4 = 1. Получим первый корень
z
1
= 2 + 4f = 6 и серию решений z = 6 + 8t, t ∈ Z .
1. y = 3, f = ((9 + 21 − 6) mod 8)/4 = 0. Получим второй корень
z
2
= 3 + 4f = 3 и серию решений z = 3 + 8t, t ∈ Z .
Случай p> 2
Рассмотрим уравнение
q(x) = (x + m)
2
− n = x
2
+ 2mx − a ≡ 0 (mod p
k
), (4.102)
при p > 2.
Обозначим через z квадратный корень из n по модулю p. Тогда,
уравнение (4.102) при k = 1 имеет корни
x = (−m ± z)(mod p).
Предположим теперь, что найдены корни x уравнения (4.102) для
произвольного k ≥ 1. Найдем корни для следующего значения k + 1. Эти
корни имеют вид y = x + p
k+1
· r, где r – неизвестное значение. Сделаем
подстановку y в уравнение (4.102):
(x + p
k+1
· r)
2
+ 2m(x + p
k+1
· r) − a ≡ 0 (mod p
k+1
).
Перепишем последнее уравнение в виде:
q(x) + 2(x + m) · p
k
· r ≡ 0 (mod p
k+1
).
Глава 4. Метод квадратичного решета                                       123

       Учитывая, что s(y) ≡ 0 (mod 2k ), поделим последнее уравнение на
2k :
                f + r ≡ 0 (mod 2), где f = [s(y)/2k ] (mod 2).         (4.101)

       Итак, получим искомое решение в виде z = y+2k ·f , где f вычисляется
по формулам (4.101).
       Выполним соответствующие расчеты для нашего примера для степени
k + 1 = 5 при y ∈ {2, 3}:
       f = ((y 2 + 807y − 214) mod 8)/4 = ((y 2 + 7y − 6) mod 8)/4
       1. y = 2, f = ((4 + 14 − 6) mod 8)/4 = 1. Получим первый корень
z1 = 2 + 4f = 6 и серию решений z = 6 + 8t, t ∈ Z .
       1. y = 3,   f = ((9 + 21 − 6) mod 8)/4 = 0. Получим второй корень
z2 = 3 + 4f = 3 и серию решений z = 3 + 8t, t ∈ Z .

Случай p> 2

       Рассмотрим уравнение

             q(x) = (x + m)2 − n = x2 + 2mx − a ≡ 0 (mod pk ),         (4.102)

при p > 2.
       Обозначим через z квадратный корень из n по модулю p. Тогда,
уравнение (4.102) при k = 1 имеет корни

                     x = (−m ± z)(mod p).

       Предположим теперь, что найдены корни x уравнения (4.102) для
произвольного k ≥ 1. Найдем корни для следующего значения k + 1. Эти
корни имеют вид y = x + pk+1 · r , где r – неизвестное значение. Сделаем
подстановку y в уравнение (4.102):

             (x + pk+1 · r)2 + 2m(x + pk+1 · r) − a ≡ 0 (mod pk+1 ).

       Перепишем последнее уравнение в виде:

                    q(x) + 2(x + m) · pk · r ≡ 0 (mod pk+1 ).

Страницы