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

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

361 = 192 . Но поскольку в ходе просеивания по первым степеням простых
чисел, эти числа em уже были поделены на 19, то надо пробежать по
интервалу [−L; L] c шагом 361 и делить не на 361, а на 19.
      Если q(x) является гладким числом, тогда после выполнения полного
просеивания, соответствующее значение W [x] станет числом, близким по
модулю к 0 (погрешность возникает из-за ошибок округления). Оценим
сейчас общую погрешность, предположим что значения логарифмов
вычисляются с точностью до , а факторная база ограничена сверху числом
B.
      На интервале [−L; L] полином q(x) = x2 + 2mx − a принимает
максимальное по модулю значение на концах интервала. Коэффициенты m
и a имеют размерность 0(n1/2 ). Считается, что L на несколько порядков
меньше m, поэтому максимальное значение q(x) имеет порядок 0(L · n1/2 ).
Если считать среднее значение размера простого числа, входящего в
разложение гладкого числа q(x), равным B/с, где c некоторая константа,
принимающая небольшие значения, например, c = 10, тогда можно
подсчитать, сколько сомножителей входит в разложение максимального
гладкого числа q(x) на интервале [−L; L]:

                 k ≈ logB/c (L2 · n1/2 ).

      В нашем примере с 34-значным числом n факторная база была
ограничена сверху числом B = 104 , c = 10, а L = 2 · 106 , тогда,

                        k ≈ log103 (4 · 1012 · 1017 ) ≈ 10.

      Таким образом, в нашем примере гладкие числа представляют собой
произведения, состоящие, в среднем, из 10 сомножителей.

Построение множества векторов показателей

      В результате самой трудоемкой и затратной по времени процедуры
просеивания в алгоритме квадратичного решета мы получим множество
чисел Smooth = {x1 , x2 , ..., xk }, принадлежащих интервалу просеивания
[−L, L], для которых значение полинома просеивания q(x) является