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

Глава 4. Метод квадратичного решета                                                     131

и занесем найденные пары (x, p) в массив Roots:

  Roots = {(1, 2), (3, 1), (5, 2), (11, 5), (17, 5), (23, 9), (29, 1), (43, 35), (47, 17),

(53, 36), (59, 7), (61, 22), (67, 39), (83, 17)}.

       3. Заполним массив Roots2, размещая в нем тройки < x, p, r >, где x
– корень уравнения q(x) ≡ 0(mod pr ) для 2 ≤ r ≤ k, pk ≤ B .
       4. Выберем радиус интервала просеивания L так, чтобы число гладких
чисел на интервале [−L; L] немного превышало размер факторной базы.
Поскольку размер факторной базы равен 14, то число гладких чисел должно
быть не меньше 16. В нашем примере, экспериментальным путем выбрано
L = 300.
       5. Определим массив W [−L .. L] из действительных чисел и занесем
в него логарифмы значения q(x), x ∈ [−L, L]. Основание логарифма можно
взять произвольным, например, a = 2 или e = 2, 71828.... Требуемая
точность вычисления логарифма зависит от длины n и не является высокой.
В большинстве случаев достаточно стандартной точности реализации с 5–6
знаками после запятой. В нашем примере достаточно хранить 2 знака после
запятой.
       6. Подготовим действительный массив LogF B[1..14], состоящий из
логарифмов соответствующих элементов факторной базы: LogF B[i] = log pi .
       II. Просеивание
       1. Выполним первое просеивание, в результате которого будут найдены
гладкие числа из интервала [−L .. L]. Для этого выполняется двойной цикл, в
котором внешний цикл берется по элементам факторной базы, а внутренний
– по числам x ∈ [−L .. L], удовлетворяющим уравнению x ≡ r(modp),
где r –корень уравнения q(x) ≡ 0 (mod p). Напомним, что все такие корни
занесены в массив Roots[1..14].
       2. Цикл просеивания для произвольного p может быть выполнен
следующим образом. Ищем корни {r1 , r2 } уравнения q(x) ≡ 0 (modp).