жения

а (Ъ) = (ар1 (Ъ),...,ар (Ъ)),

а также двоичный вектор, полученный из вектора а(Ъ) приведением всех его координат по модулю 2,

£(Ъ) = (ар1 (Ъ) mod 2,..., aph (Ъ) mod 2).

Если теперь каким-либо способом подобрать такое множество различных теел Ъ.,... ,Ът, при котором выполняется линейное соотношение

ё{Ъ1) © ... © ё{Ът) = 0, то для произведения x = Ъ. .. .Ът выполняется соотношение

x2 = y2 (mod и),

y=Y[ pbirAbi)+-+<iAbr.)) peB

Алгоритм Диксона заключается в следующем.

Шаг 1. Выбрать случайное Ъ, 1 < Ъ < геислить Ъ2 mod m.

Ъ2 mod m

простые множители из факторной базы. Шаг 3. Если гается В-числом, т.е.

Ъ2 mod и =Y[ pap(b), peB

то запомнить а(Ъ) и £(b). Повторять процедуру генерации Ъ m=h+1 B

Ъ1,...,Ът-

Шаг 4. Найти (например, решая с помощью алгоритма последовательного исключения неизвестных Гаусса однородную систему линейных уравнений Xle(Ъl) ©...©xme(Ъm) = 0 относительно неизвестных (xi,..., xm)) соотношение линейной зависимости

e(Ъil) © ... © e(Ъit ) = 0, Положить

1 <t € m.

x = Ъil ...Ъit,

((Sp(b,J+... + ap(b,J)

pe B

Шаг 5. Проверить x = ±у (mod и). Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение

и = u - v, u = (x + у, и), v = (x - у, и).

На трудоемкость алгоритма Диксона существенно влияет выбор факторной базы. Если число h выбрано так, что М « то почти каждое число ет В-числом, но получаемые при этом сравнения x2 = у2 (mod и) будут тривиальными. Кроме того, надо будет решать

и x2 = a2

(mod и)

(x, у)

с x = ±у (mod етосходит 1/2. Следовательно, повторяя про-

что надежность данного метода нахождения делителя не меньше,

1 - 2-k

Обозначим через (и,М етых чисел тервале 1 < <a € и, раскладывающихся в произведение простых чисел из множества В = {p: p € М}.

Из результатов Н.Де-Брейна (1966) и Е.Кэпфилда, Р. Эрдоша и К. Померанца (1983) вытекает следующая

>

> 0, x 10, u € (log x)1- щи u ерно по x выполняется соотношение

x,x}/ = x - u-u(1+o(1)). Отсюда при и = jl получаем

(x,y)= x - u-u(1+o(1)).

Поэтому в качестве приближенного значения вероятности получения числа, раскладывающегося в произведение простых чисел из множества В = {p: p € М}, при случайном выборе чисел в интервале [2, и]

где и = Yjj. Эту же величину можно принять в качестве приближенного значения вероятности появления В-числа на шаге 1 алгоритма.

Всего надо набрать h + отчных В-чисел, причем при их про-

временную арифметическую сложность алгоритма Диксона можно оценить выражением

T = Oa(uu • h2 + h3),

где Oa (h3) - отения системы из h+1 линейных уравнений от h неизвестных. В нашем случае h = тг(М) = ij-

Выберем в качестве М величину М = Ь{пу/, где через Ь{п) обозначено ехр(\/1пп In In п). Тогда, как нетрудно проверить,

uu = L(n)1/2, M = n(M) = L(n)1/2

Отсюда следует, что трудоемкость алгоритма Диксона оценивается следующим образом:

T = Oa (L(n)2 + L(n)3/2) = 0(L(n)2 )

Алгоритм Диксона может быть усовершенствован по нескольким направлениям:

- можно заменить процедуру генерации В-чисел так, чтобы вероятность их порождения была большей;

- можно оптимизировать выбор факторной базы с тем, чтобы уменьшить число неизвестных в системе уравнений;

не являющихся В-числами;

- можно использовать быстрый алгоритм решения системы линейных уравнений (например, алгоритм Видемана для разреженных матриц), и т.д.

Подобные улучшения не позволяют изменить общий вид оценки сложности 0(L(n)c та уменьшить константу е, c > 1.

13.5. Алгоритм Врилхарта-Моррисона

Суть алгоритма Врилхарта-Моррисона, опубликованного ими в 1975 г., заключается в двух изменениях в алгоритме Диксона:

ных дробей, предложенного Лагранжем, позволяющего генерировать

6 62 mod n

его разложения более высока;

б) из факторной базы тся те числа p, для которых

= -1.

Рассмотрим его более подробно.

Теорема. Пусть ж > 1 - действительное число, « { } последовательность его подходящих дробей, k =1,2, при всех k 1 выполняется неравенство

P2 - x2Qk < 2x Доказательство. В силу свойств подходящих дробей имеем

Pk2 - x2Qk=

Отсюда

P2 - x2Qk- 2x< 2x •

<

Qk Qk+1

k Qk+i /

Qk+:

<2x• -1 V

2Qk+iy Qk + 1 \

<

Qk+1;

< 2x

Qk+1

Qk+1

подходящая

2 < 2\/n. Поэтому минимальный

дробь для числа \[п. Тогда минимальный по абсолютной величине вычет Р mod п равен Р - nQ\ и не превосходит Доказательство. При ж = /п

Pi{Pi-nQl) (modn),

причем в силу теоремы Р - nQ/.

Pk2 - nQ2k

Данное следствие показывает, что если в качестве случайных чи-6 Pk

Pk2 mod n Pk2 - nQ2k

будет превышать значения Поэтому вероятность его разложе-

случайном выборе.

факторной базы все числа р, у которых () = - 1. Покажем, что в раз-Pk2 - nQ2k

только те числа таторых и является квадратичным вычетом

Пусть p (P22 - uQI как (Pk,Qk) = (p,Qk) = 1- Отсю-

Qk p

выполняться условие

{PkQ--1)2 = и (mod p),

но это и означает, что () = 1.

Такие улучшения позволяют добиться общей оценки сложности алгоритма 0{Ь{пУ) при с= \/2.

13.6. Метод квадратичного решета

пользовать подход, обобщающий метод Ферма. Рассмотрим функцию

f{x) = {x+lV\f -п,

являющуюся квадратным трехчленом с целыми коэффициентами. При каждом целом x £ Z получается нетривиальное сравнение

(x+LvJ)2/(x) (modn),

/(x) x

/(ж) < ж2 + 2жу,

и поэтому (ж + [л/й]) 7 /(ж). Поэтому, если при вместо случайных чисел отатривать значения Ъ = / (x) при случайных текотором интервале -М € x € М, то вероятность В

/( x)

жители из факторной базы для каждого p £ В, которое

может выступать в качестве сомножителя в разложении

f{x) = {x+lV\f-п=1[р"(х\

pe B

решаем квадратное уравнение

(ж+ [Vn\f -п = 0 (modp)

в кольце &ли rlp),r2 -решения этого уравнения, то должно выполняться равенство x = r1 + jp, i = 1, 2, j £ Z.

Проделав предварительно данную работу по нахождению кор-r1lp) , r2lp) p £ В

ле [-М, М е чиела ых сравнение x = r1lP) (mod p)

p£ В

x p£ В

/(x)

если она существует.

Дж.Дэвис и П.Монтгомери обобщили данный подход. Они предложили использовать многочлен

/ab(x) = ax2 + 2Ъx + c,

a, Ъ, c

условию

Ъ2 - ac = и, 0 € Ъ <a; При таком выборе коэффициентов выполняется равенство

a/ab(x) = (ax + Ъ)2 - и, откуда получаем сравнение

(ax + Ъ)2 = a/ab(x) (mod и),

причем

(ax + Ъ)2 = a/ab(x).

a, Ъ, c /ab(x)

[-М, М]

fab{-M)-{a2M2 -п).

Минимальное значение она принимает в точке x = -Ъ/ -1 < x < 0,

( Ъ \