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

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

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

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

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

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

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

или

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

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

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

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

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

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

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

число d такое, что (^) = 1 и d < ?

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

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

Из равенств Ь2 4ас = D и а = d2 следует сравнение

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

Таким образом, для каждого простого числа 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.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >