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

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

оно, вероятно, простое, и отбрасывается (хотя, при этом одновременно
отбрасываются и многие составные числа). Если же число проходит проверку,
то оно является детерминированно составным числом и подвергается
разложению на множители, меньшие B 2 каким-нибудь несложным методом
факторизации типа ρ–метода Полларда.
      Дальнейшее развитие идеи больших множителей до трех или
более множителей вызывает дополнительные сложности и считается
неэффективным.


4.9. Варианты           метода         квадратичного              решета        с
      возможностью распараллеливания
     Одним    из    благоприятствующих       факторов,     выделивших       метод
квадратичного решета среди других методов, явилась возможность
распараллеливания     процесса    вычисления     на   несколько       компьютеров
(процессоров). Для этого П.Монтгомери была предложена идея метода
квадратичного решета с использованием множества полиномов (multiple
polynomial quadratic sieve MPQS).
      Рассмотрим полином:

  za,b (x) = (ax + b)2 − n = a2 x2 + 2abx + b2 − n,   где a, b ∈ Z.        (4.117)

      Как и раньше, просеивание будет выполняться при различных
значениях x в интервале [−L, L]. Наибольшее значение полинома za,b (x)
при x ∈ [−L, L] примерно равно a2 K 2 − n, наименьшее примерно равно
                  p
−n. Если взять a ≈ 2n/M , то наибольшее и наименьшее значение станут
примерно равны по абсолютному значению. Число b нужно выбрать таким
образом, чтобы b2 − n делилось на a, то есть выполнялось b2 − n = ac, c ∈ Z.
Тогда полином (4.117) можно записать в виде

       za,b (x) = a(ax2 + 2bx + c).

      Это гарантирует, что каждое просеиваемое значение будет делиться
на a. Пусть a = t2 , t ∈ Z. Если некоторое произведение значений полинома