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

Глава 5. Метод решета числового поля                                        168

         Теперь выражений для многочлена g(x) (5.143) получит вид
                       Y
g(α) = (f 0 (α))2 ·          (a−bα) = (f 0 (α))2 µs νs2
                       x∈S
                                                                         (5.149)
и теперь вместо извлечение квадратного корня из g(x) достаточно вычислить
                                                 √
корень из µs и перемножить три полинома f 0 (x), µs и νs .
         Авторы этого метода заметили, что практическая польза от этой идеи
вычисления корня полностью не ясна, и окончательный вердикт должен быть
вынесен после ее реализации.

       4. Завершение вычисления

        Теперь мы можем завершить полную задачу факторизации числа n =
45113.
         Вычислим сначала произведение
                   Y
y 2 = f10 (m)2 ·       (a−bm) = (3·312 +30·31+29)2 ·(−1+31)(3+31)(13+31)(104+31)·
               x∈S

(3+2·31)(−8+3·31)(48+5·31)(54+5·31)(−43+6·31)(−8+6·31)(−8+7·31)(11+7·31)·

(856+11·31) = 38422 ·317465033886002 mod n,

откуда y = 3824 · 31746503388600 mod 45113 = 15160. Пара чисел (x, y) =
(43992, 15160) удовлетворяет уравнению x2 ≡ y 2 mod n, откуда x2 − y 2 =
(x + y)(x − y) = (43992 + 15160)(43992 − 15160) = 59152 · 28832.
         Вычисляя теперь с помощью алгоритма Евклида наибольший общий
делитель Н.О.Д.(n, x ± y), найдем делители n = 45113:
         Н.О.Д.(n, x + y) = Н.О.Д.(45113, 59152) = 229,
         Н.О.Д.(n, x − y) =Н.О.Д.(45113, 28832) = 197.


5.6. Оценка сложности решета числового поля
         Общее время работы алгоритма решета числового поля зависит от
времени работы составляющих его частей, из которых наибольший вес
имеют время первичного просеивания, в ходе которого ищутся номера