13.1. Метод Полларда

Наиболее популярным вероятностным алгоритмом факторизации является так называемый «рметод», предложенный Дж.Поллардом в 1975 г.

Алгоритм 1

Шаг 1. Выбираем многочлен /(x) € Z[x тесло ш.

Шаг 2. Случайно выбираем xo € Z n xi =

= /(xi-1) mod n i = 1, ,m, проверяем тест шага 3.

Шаг 3. Для po+2kr тагаем j=2h - каждого 2h<k<2h+1 вычисляем d =(xj - xk, &ли 1 <d<n, то нетривиальный

n d=1 d=n

к следующему значению h.

Чтобы оценить среднее время работы данного алгоритма, рассмотрим сначала более простой для анализа, но менее эффективный алгоритм, отличающийся от алгоритма 1 тем, что на шаге 3 вычисляется HOД(xj - xk, теел пар чисел j, k О < j<k < m. Назовем его Алгоритм 2.

Воспользуемся известным «парадоксом дней рождения».

Теорема. Пусть А > 0. Для случайной выборки из п элементов объема / + 1, где I = л/ЗАп, вероятность того, что все элементы в выборке будут попарно различными, допускает следующую оценку сверху:

Доказательство. Имеем

Pnl =

n(n - 1) (n - 1) л л

i=i V

1 - -

log(1 - x) < -x О < x< 1

получаем

log pni <

1(1 + 1) 2п

□

xo, x1,

,xm xi = /(xi-1) j = 1,,m, как случайную выборку. Для случайного отображения /: Zn Zn это оправдано. Хотя многочлен / (x) € Z[x], конечно, нельзя рассматривать как случайное отображение, тем не менее, практические результаты говорят о хорошем соответствии приведенных ниже оценок трудоемкости с теми, которые получаются в действительности.

pn p (xj - xk, мо уел овию p (xj - xk га и xj = xk (mod p). Поэтому, применяя доказанную выше теорему для выборки, образованной последовательностью ,x вде xi = xi modp, получаем, что при / = \j2\n вероятность существования пары i,k, Q <к 1 такой, что p (xj - xk, меньше, чем 1 - е-А.

Так как р < Jn, то вероятность одновременного выполнения ра-xj = xk (mod n) xj = xk

(mod n) n

Таким образом, для нахождения данной пары с надежностью 1 - e- то вычислить 1 + едовательности {xi}, где I = л/2Ар. Отсюда средняя сложность алгоритма 2 оценивается величиной 0(Р log3 п) = 0(Avlog3 п).

Перейдем теперь к рассмотрению алгоритма 1. Заметим, что поскольку / (x) -отлен над ото делителя тела n и любой пары О j < товием xj = xk (mod p) будут выполняться и сравнения xj+i = xk+i (mod xj+2 = xk+2 (mod p) и т.д.

( j, k )

(xj - xk, n) = довательность длины 1 + 1. По-

( j, k)

условием (xj - xk, n) = вде j = j + s k = k + жотором s, где j, k) k < 4k

двоичной записи 1 + т. e. 2h < k < 2h+1. Тогда при j = 2h+1 - тело k = k + (j - j) будет находиться в интервале 2h+1 < k < 2h+2, поскольку

k = k + (j - j) < 2h+1 + 2h+1 - 1 - j < 2h+2,

причем так как 2h o k < 4k.

В таком виде алгоритм «пробных делений» входит составной частью практически во все современные методы факторизации.

что оно не простое. Это можно сделать с помощью одного из описанных выше тестов простоты. Их трудоемкость, как правило, значитель-

будет заведомо считаться составным.

Таким образом, если второму алгоритму потребуется последова-l+1 4l + 1

оценивается уже величиной 0(vA/nlog п), что гораздо лучше, чем 0(Avlog п). Тем самым доказана

иС такая, что для любого положительного числа X вероятность события, состоящего в том, что р-метод Полларда не найдет нетриви-и Сл/Alog и

ны e .

13.2. Алгоритм Полларда-Штрассена

Алгоритм Полларда-Штрассена является детерминированным алгоритмом для нахождения минимального простого делителя и имеет оценку сложности 0(log п). Он основан на следующей теореме.

Теорема. Пусть z £ N, у = z2 я любого t £ N наименьший простой делитель числа (t,yl) может быть найден за 0(z log2 z log21) двоичных операций.

Доказательство. Сгруппируем сомножители в выражении

у1 = (1 - 2 - ... - z)[(z + 1) - ... - (2z + 1)] ... [((z - 1)z + 1) - ... - z 2] =

= П((7 = /(1)/(2)---/(-)-

/(j) = ((j - 1)z + 1) . . . ((j - 1)z + z) j = 1, . . . , z

нахождения наименьшего простого делителя числа (t, у\) можно воспользоваться следующим способом:

/(1), . . . , /(z)

( t, /( j)) j = 1 , 2, . . . , z нетривиального делителя.

(t, /(j))

на числа (j - 1)z + 1,..., (j - 1)z + z. Первое число из это-

(t, /(j))

минимальным простым делителем числа (t,y\).

Оценим теперь сложность выполнения каждого шага. Для выполнения первого шага найдем коэффициенты многочлена

/ (x) = ((x - 1)z + 1) ... ((x - 1)z + z).

Воспользуемся алгоритмом быстрого дискретного преобразования

и т. д. в итоге получается

log z

-2Mog2<zlogz

арифметических операций. При его выполнении необходимо выполнять операции сложения и умножения целых чисел. Заметим, что

/(j) mod t

здесь выступают умножение и деление с остатком, имеющие слож-0(log2 t)

0( z log2 z log2 t)

полняется по той же схеме, только в качестве линейных сомножителей выступают многочлены (x-X),..., (x-z). Поэтому сложность первого этапа равна 0(z Xog z Xog t).

нахождения НОД целых чисел. Двоичная сложность алгоритма на-log t 0(log2 t)

0(z log2 t)

log t 2 log z

этого этапа равна 0(2; log t log z). Теорема доказана. □

Для факторизации числа п следует положить z = [/nj +1, y = z2, t = и, откуда вытекает, что сложность нахождения наименьшего простого делителя числа п данным алгоритмом равна 0{-n\og4 п) двоичных операций. Если положить z < Y\/n\ + 1, то алгоритм будет

Заметим, что современные методы факторизации на практике часто выполняются в 3 этапа.

Этап 1. Пробные деления на 1 2 тысячи первых простых чисел.

Этап 2. Нахождение маленьких простых делителей методом Пол-

рается из соображений оптимизации общей трудоемкости алгоритма).

Этап 3. Для нахождения больших простых делителей применяется один из субэкспоненциальных алгоритмов.

13.3. Факторизация Ферма

Весьма плодотворной идеей при построении алгоритмов фактори-

соотношение x2 = у2 (mod при этом x = ±у (mod n), то числа (x + у, n) (x - у, n) n

По-видимому, первым в этом направлении является метод факторизации, примененный П. Ферма. Он основан на теореме Эйлера о представлении числа в виде разности двух квадратов. n> 1

ное соответствие между разложениями на множители n = а • 6, а 6 > О тде разности квадратов n = x2 - у2, x > у > 0. Это соответствие имеет вид

а = x + у, 6 = x - □

Метод Ферма заключается в том, что при малых значениях параметра ставлении n=x2 - тайти пару (x, у), перебирая в качестве кандидатов на значение х числа [л/й] + 1, LvJ + 2,... и проверяя для каждого из них равенства

(LvJ

i)2 - n = y2

что если число не является квадратом, то оно с большой вероятностью не будет и квадратичным вычетом для одного из небольших простых p

ответствующего символа Лежандра.

n p1 , , pk

pi n i = 1 , , k

Шаг 1. Для каждого х от [л/й] + 1 до [л/й] + о вычислить величины

t = x2 - n, ti = t mod pi, i = 1,,k i = 1, , k

условий:

ti = О pi2 t

перейти к шагу 3.

Шаг 3. Проверить, является ли t = x2 - n полным квадратом. Если x2 -n=еть ответ: «n - ставное, n=а-6 а=x+у.

6 = x - сли t = x2 - n - не полный квадрат, то перейти

По сути, данный алгоритм, подобно методу «пробных делений», является разновидностью метода перебора всех возможных делителей. Сложность этого алгоритма оценивается величиной O(no log2 n). no

можных делителей будет проверено. Однако, в отличие от метода «пробных делений», с помощью которого находится наименьший делитель, данный метод позволяет находить наибольший делитель числа п, не превосходящий /п.

Заметим, что вместо /n можно брать \/fcn при малых значениях к. Во многих случаях переход к уравнениям ([\/fcnJ +«)2-fcn = a;2, k = 3, 5, x

кого перебора значений при k = 1. При этом, в случае успеха

числа

{[\/кп\+г + х), {[Vknl+i-x) (О, n)

([л/кп] + г + х){ [л/кп] + г - х) = кп. 13.4. Алгоритм Диксона

Во многих современных алгоритмах факторизации для нахождения делителей используется идея Лежандра (1798 г.), заключающаяся в поиске пары целых чисел и у, удовлетворяющих условиям

x2 = у2 (mod n), x = ±у (mod n)

Этот подход является обобщением метода Ферма, в котором требуется выполнение строгого равенства.

Для поиска таких чисел воспользуемся понятием факторной базы.

Назовем факторной базой некоторое множество B = {pi,p2, ,ph} небольших простых чисел. Обычно в качестве pi,p2, ,ph берут простые числа, не превосходящие некоторой границы h = n(M).

Будем говорить, что целое число 6 € гается В-числом, если 62 mod n ной базы:

62 mod n =

pap(b)