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

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

Первичное просеивание для n = 45113

       Для нашего примера n = 45113 выберем линейное просеивание со
значением L1 = 1000 и b, принимающим значения 1, 2, ..., пока не будет
найдено более 40 гладких чисел. Поместим найденные гладкие числа в табл.3.

                                                                               Таблица 3
             Гладкие числа, найденные на этапе предпросеивания
        (a, b)    (a, b)    (a, b)    (a, b)      (a, b)      (a, b)        (a, b)
       (73,1)     (2,1)     (1,1)     (2,1)       (-3,1)      (-4,1)        (-8,1)
       (-13,1)   (-14,1) (-15,1)     (-32,1)     (-56,1)     (-61,1)       (-104,1)
      (-116,1)    (5,2)     (-3,2)   (-25,2)     (-33,2)      (8,3)         (-2,3)
       (-17,3)   (-19,4) (-48,5)     (-54,5)     (-313,5)     (43,6)        (8,7)
       (-11,7)   (-38,7) (-44,9)     (-4,11)    (-119,11) (-856,11) (-536, 15)
       (-5,17)   (-5,31) (-9,32) (202,43)        (-24,55)

       Этот этап называется предварительным просеиванием, поскольку он
позволяет только найти номера гладких пар, а не сами разложения (хранить
вектора разложения для всех чисел из интервала просеивания является
неэффективным). Для нахождения самих векторов разложений нужно
выполнить повторное просеивания только уже не по области просеивания, а
по множеству найденных номеров гладких чисел. В результате будут найдены
представления каждого из чисел F1 (a, b) и F2 (a, b) уже в виде произведения
элементов соответствующих факторных баз.

Вторичное просеивание для n = 45113

Выполнив вторичное просеивание найдем множество гладких пар M .
Рассмотрим пример элемента такого множества.

F2 (8, 3) = 8−3m = −85 = −20 ·30 ·51 ·70 ·110 ·130 ·171 ·190 ·230 ·290 ,

что соответствует вектору разложения

       v(8, 3) = (1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0)