Алгоритм с несколькими многочленами

Неприятная особенность алгоритма Померанса заключается в определении длины интервала 1. Если интервал слишком большой, то значения многочлена f (x) становятся очень большими и недостаточно часто раскладываются в произведение элементов факторной базы. С другой стороны, если интервал 1 слишком мал, то количество найденных соотношений (13.23) может оказаться недостаточным.

Наиболее очевидным решением данной проблемы является использование в алгоритме решета не одного многочлена /(ж), а нескольких многочленов, выбранных случайным образом из введенного нами ранее множества F_m. Кроме того, целесообразно фиксировать длину интервала 1 гак, чтобы значения многочленов на данном интервале не превышали некоторой фиксированной величины.

Эти идеи были высказаны независимо Питером Монтгомери (Peter Montgomery), а также Джеймсом Девисом (James A. Davis) и Дианой Холдридж (Diane В. Holdrige), впервые реализовавшими алгоритм квадратичного решета па практике^[1].

В 1987 году вышла статья^[2] Роберта Сильвермена (Robert D. Silverman), в которой был предложен эффективный алгоритм построения многочленов. В настоящее время алгоритм Сильвермена называют алгоритмом квадратичного решета с несколькими многочленами (MPQS — multiple polynomial quadratic sieve).

Рассмотрим многочлен /(ж) = ах² + Ьх + с € Т_т с положительным старшим коэффициентом а > 0. Будем считать, что для дискриминанта данного многочлена выполнено сравнение т = Ь²—4ас.

Для данного многочлена f (x) мы можем записать сравнение.

или

последнее сравнение является сравнением Крайчика. Легко видеть, что предложенный Помсрансом многочлен /(ж) = (ж + /г)² — т является частным случаем рассматриваемого класса многочленов.

Поскольку выполнено условие а > 0, то многочлен /(ж) имеет минимум, который достигается в точке ж = — Выберем эту точку в качестве середины интервала X, на котором рассматриваются значения многочлена /(ж), и определим его длину таким образом, чтобы абсолютные значения многочлена /(ж) в точке минимума и на границах интервала совпадали. Тогда выполнены равенства.

Поскольку / (-?) = -g. а / (-? — |)=/(-? + {) = -" + «?. то из условия (13.26) следует равенство.

Полученное равенство связывает между собой старший коэффициент многочлена /(ж) и длину интервала X, на котором проходит поиск значений, удовлетворяющих равенству (13.19). Стоит отметить, что из (13.27) следует, что на всем интервале X выполнена оценка.

Поскольку величины a, S являются положительными целыми числами, то при практических вычислениях равенство (13.27) не может быть достигнуто. Поэтому величина 6 фиксируется исходя из возможностей вычислительной техники, а равенство (13.27) заменяется неравенством а ^ .

Способ построения случайного многочлена

Теперь мы опишем процедуру выбора коэффициентов многочлена /(х) € Д_т- Вначале выберем случайное нечетное простое число d такое, что (^) = 1 и d < ?

Определим коэффициент а равенством а = d², тогда из (13.25) следует сравнение.

Мы снова получили сравнение Крайчика, в котором левая часть удовлетворяет неравенству (13.28).

Из равенств Ь² — 4ас = D и а = d² следует сравнение.

которое позволяет определить значение вычета Ь. Теперь свободный член с многочлена /(х) определяется равенством с = .

Таким образом, для каждого простого числа d. мы получаем тройку (а, Ь, с), определяющую коэффициенты многочлена /(х).

• [1], 0 См. Davis J.A. and Holdridge D.B., Factorization Using the Quadratic SieveAlgorithm // Sandia National Laboratories. — Albuquerque, New Mexico. — 1983.
• [2] Cm. Silverman R.D. The Multiple Polinomial Quadratic Sieve // MathematicsOf Computation. — №. 177. — Vol. 48. — 1987. — pp. 329−339.