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

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

q(x) = ax2 + 2bx + c является полным квадратом
       Y
             (ax2 + 2bx + c) = A2 ,
       x∈M

тогда полным квадратом будет и произведение
     Y                  Y
           za,b (x) =         t2 (ax2 + 2bx + c) = (tA)2
     x∈M                x∈M

      Просеивание будет проводиться среди 2L + 1 значений полинома
q(x) = za,b (x)/a = ax2 + 2bx + c, каждый из которых ограничен сверху
             p
значением L n/2. Делимость b2 − n на a означает, что b2 ≡ n(mod t2 ).
Если выбрать число t простым, так чтобы n было квадратичным вычетом
по модулю t, то b можно легко вычислить по алгоритму Шенкса.
      Следующий вопрос состоит в том, насколько большим нужно брать
L. При большом значении L на каждом полиноме будет просеиваться много
чисел большого размера, среди которых гладких чисел будет сравнительно
мало, что нежелательно. Если взять L малым, то числа для просеивания
также будут небольшими, но нужно генерировать большое количество
полиномов, подбирая коэффициенты a,b. Но для каждого нового полинома
нужно заново формировать факторную базу, т.е. заново выполнять этап
инициализации, что также является затратной процедурой. Таким образом,
если L слишком мало, то большая часть времени будет тратиться не на
просеивание, а на инициализацию полиномов. Если удастся сократить время
инициализации, то можно будет использовать меньшие значения L.

Самоинициализирующееся квадратичное решето

     Алгоритм самоинициализирующегося квадратичного решета (self ini-
tializing quadratic sieve) позволяет менять полиномы за малое время, что
дает возможность использовать меньшие значения L, нежели в алгоритме
квадратичного решета с множеством полиномов. Основная идея метода
состоит в том, чтобы использовать несколько полиномов с одним и тем же
значение параметра a и различными b, 0 < b < a/2.