<< Предыдущая

стр. 33
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

этого факта. Другими словами, данное число уже выдержало тест
Миллера - Рабина по нескольким основаниям и все, что остается —
это доказать его простоту.
Наиболее успешный из алгоритмов, доказывающих простоту, ос­
новывается на эллиптических кривых и называется ЕСРР (от англ.
Elliptic Curve Primality Prover). В свою очередь, этот алгоритм осно­
вывается на более старом алгоритме доказательства простоты, при­
надлежащем Поклингтону и Лемеру. Его вариант, опирающийся на
эллиптические кривые, был разработан Гольдвассером и Килианом.
Алгоритм ЕСРР случаен, т. е. нельзя гарантировать с математиче­
ской точностью, что он всегда выдаст ответ — свидетеля, доказы­
вающего простоту введенного в него простого числа. Если число,
подаваемое на вход алгоритма, составное, то вообще нет уверенно­
сти в том, что алгоритм когда-либо остановится. Хотя алгоритм
ЕСРР работает занимает полиномиальное время, т.е. он довольно
эффективен, проверку получаемого им свидетеля простоты данного
числа можно произвести еще быстрее.
Есть алгоритм, авторы которого — Адлеман и Хуанг. В отли­
чие от алгоритма ЕСРР он гарантирует окончание работы и до­
казательство простоты введенного простого числа. Метод основы­
вается на гиперэллиптических кривых, обобщающих эллиптические
кривые и, насколько мне известно, никогда не был реализован. Алго­
ритм Адлемана и Хуанга никогда не осуществлялся не только из-за
своей сложной математической структуры, но и потому, что несмо­
тря на отсутствие уверенности в получении ответа, метод ЕСРР
на практике дает тот же результат, что и алгоритм, основанный на
гиперэллиптических кривых, но с гораздо меньшими усилиями.


8.2. Алгоритмы факторизации

Методы разложения на множители (или факторизации) можно раз­
делить на средневековые методы, такие как
- пробное деление,
- {Р — 1)-метод,
- (Р + 1)-метод,
- р-метод Полларда;
и современные:
Глава 8. Тесты на простоту и факторизация

- метод непрерывных дробей (CFRAC)^
- квадратичного решета,
- квадратичного решета в числовом поле.
Ни время, ни объем книги не позволяют нам обсуждать все эти
методы подробно. Поэтому мы ограничимся парой средневековых
методов и объясним основные идеи, питаюш;ие некоторые из совре­
менных алгоритмов.
Время работы современных алгоритмов лежит где-то между по­
линомиальным и экспоненциальным, т.е. в суб-экспоненциальной
области. Их сложность измеряется функцией
L ^ ( a , ^ ) = e x p ( ( ^ + o(l))(lniV)^(lnln7V)i-^).
Заметим, что
- Ljv(0,/3) = {In N)^˜^^^^^ — полиномиальная сложность,
- 1/дг(1,^) = А/'^+^(1) — экспоненциальная сложность.
Так что, как было замечено в главе 7, при О < а < 1 функция
Ь^{а^^) описывает сложность, лежащую между полиномиальной и
экспоненциальной. Приведем оценки сложности некоторых алгорит­
мов факторизации в терминах этой функции.
- Наиболее медленный алгоритм, алгоритм пробного деления,
имеет сложность Ь^{1^ 1/2)-
- До начала 1990-ых годов самым быстрым из общих методов
факторизации был метод квадратичного решета со сложно­
стью L7v(l/2, с) с некоторой константой с.
- Сложность наиболее приемлемого алгоритма на сегодняшний
день, метода квадратичного решета в числовом поле, равна
Хдг(1/3,с), где с — константа, не зависящая от разлагаемого
числа N,

8 , 2 . 1 . П р о б н о е деление
Пробное деление — это самый элементарный алгоритм факториза­
ции. Для разложения числа N на множители поступают следующим
образом:

for (р=1; p<sqrt(N); р++)
{ е=0;
if ((N mod р)==0) then
{ while ((N mod p)==0)
8.2. Алгоритмы факторизации 217

{ е=е+1;
N=N/p;
}
вывести ( р , е ) ;
}
}

Даже поверхностное знакомство с алгоритмом показывает, что в
самом плохом случае, — случае простого iV, — он требует 0{y/N)
операций. Размер входных данных пропорционален log2 AT, т. е. этот
алгоритм имеет экспоненциальную сложность. Но совсем пренебре­
гать этим методом не стоит. Он вполне приемлем для разложения
чисел, не превосходящих 10^^.

8.2.2. Гладкие числа
Для факторизации больших чисел хотелось бы иметь на вооруже­
нии что-то более быстрое, чем пробное деление. Практически все
остальные алгоритмы используют вспомогательные числа, называ­
емые гладкими. По существу, к гладким относят те числа, которые
легко раскладываются на множители методом пробного деления.
Уточним этот термин.

Определение 8.2. (Гладкие числа.) Пусть В — целое число.
Число N называется 5-гладким, если любой его простой делитель
меньше, чем В.
Например, число


является 12-гладким. Иногда мы будем называть число просто глад­
ким, если граница В его гладкости мала по сравнению с самим чи­
слом.
Количество у-гладких чисел, не превосходящих х, обозначается
через ф{х,у). Это довольно сложная функция, которая аппроксими­
руется как
ф{х,у) ^хр{и),
где р — функция Дикмана-Де Брюина и
1п:г
и= -—.
In у
Функция Дикмана-Де Брюина определяется как решение диффе-
Глава 8. Тесты на простоту и факторизация

ренциального уравнения
up'{и) -^ р{и-\) =0
при U > 1. В частности, р(и) можно аппроксимировать выражением
р{и) ^ и˜'^,
которое имеет место при и —^ оо. Это подводит нас к результату,
важному при анализе современных алгоритмов факторизации.

Теорема 8.3. Доля :г^/^-гладких целых чисел, не превосходящих х^
асимптотически равна г/˜^.
Положив теперь у = 1/дг(а,/?), мы получим
InN 1 / IniV ^ ^-"^
и = 1пу /3 VlnlnTV
Отсюда можно вывести, что

—ф{N^y) ^ и˜'^ = ехр(—wlnn) =

где 7 — какая-то константа. Предположим, что нас интересуют чи­
сла, меньшие 7V, которые являются Z/7v(a, /?)-гладкими. Вероятность
того, что любое число, меньшее 7V, действительно ^дг(а, ^)-гладкое,
равна 1/Lj\[{l — а,7)- Это, будем надеяться, объяснит на интуитив­
ном уровне, почему сложность некоторых современных методов раз­
ложения на множители приблизительно равна L7v(l/2,c). В квадра­
тичном решете в числовом поле получается более высокая скорость
только благодаря усложненному математическому алгоритму.
При дальнейших обсуждениях нам потребуется понятие показа-
тельно В-гладких чисел.

Определение 8.4. (Показательная гладкость.) Число N назы­
вают показательно В-гладким, если любая степень простого числа,
деляш;ая N^ меньше В.
Например, число N = 2^ 3^ является показательно 33-гладким,
т. к. максимальная степень простого числа, деляш;ая JV, — это 2^ = 32.

8.2.3. ( Р — 1 ) - м е т о д П о л л а р д а
Самое известное имя конца двадцатого века, связанное с алгорит­
мами факторизации, — это имя Джона Полларда. Практически все
важные продвижения в факторизации были сделаны им, например,
- ( Р — 1)-метод,
8.2. Алгоритмы факторизации

- р-метод,
- метод квадратичного решета в числовом поле.
В этом параграфе обсуждается {Р — 1)-метод, а в следующем мы
рассмотрим метод квадратичного решета в числовом поле, оставив
остальные методы в качестве упражнений.
Пусть число TV, которое мы планируем разложить на множители,
равно произведению двух простых N = р - q. Кроме того, будем
считать, что нам известно такое целое число 5 , что р — 1 является
показательно J5-глaдким, а. q — l таковым не является. Тогда можно
надеяться, что р — 1 делит 5!, в то время как ^ — 1, скорее всего,
этого числа не делит.
Предположим, что мы нашли
А = 2^' (modiV).
Представив себе, что мы можем подсчитать то же самое по модулям
р и q^ мы получим
А = 1 (modp),
поскольку р—1 делит В\ и, по малой теореме Ферма, Л^˜^ = 1 (modp).
С другой стороны, равенство
А = 1 (mod q)
маловероятно. Следовательно, р делит А — 1, а, q этого числа не
делит. Поэтому можно восстановить р, вычисляя ПОД (Л — 1, N).
На псевдокоде этот алгоритм выглядит следуюш;им образом:

А=2;
for (j=2; j<=B; j++)
{ A=A^j mod N; }
р=Н0Д(а-1,Ю;
if (p!=l и p!=N) then
вывести: «p делитель N»;
else
вывести: «результат не получен»

Попытаемся разложить на множители число N = 15 770 708441.
=
Выберем J9 = 180 и прогоним этот алгоритм. В результате получим
А = 2^' (modiV) = 1162 022425.
Применяя алгоритм Евклида, найдем
р = ПОД {А -1,N) = 135 979.
Глава 8, Тесты на простоту и факторизация

Обратите внимание на то, что в нашем примере N = 135 979-115 979.
Поэтому
р - 1 = 135 979 - 1 = 2 • 3 • 131 • 173,
^ - 1 = 115 979 - 1 = 2 .103 • 563.
Следовательно, р—1 действительно показательно 180-гладкое и даже
174-гладкое, в то время как q — 1 таковым не является.
Можно показать, что сложность {Р — 1)-метода оценивается как
0{BlnB{lnNf -\- (InNf).
Значит, выбор В = 0{{\пМУ) при некотором натуральном i обес­
печивает полиномиальную сложность алгоритма, даюш;его, правда,
результат только для чисел специального вида.
Ввиду суш;ествования {Р — 1)-метода Полларда для алгоритма
RSA рекомендуют выбирать простые числа вида
p = 2pi + l и ^ = 2^^! + 1,
где pi, ^1 — тоже простые. В этой ситуациирид называются заш;и-
ш;енными простыми. Однако такая рекомендация сегодня не явля­
ется строго необходимой, если в приложениях RSA используется
большой модуль. Дело в том, что слишком мала вероятность числу
р — 1 оказаться показательно 5-гладким с малым В, если р выбрано
случайным образом и насчитывает 512 двоичных знаков. Следова­
тельно, выбор случайного 512-значного двоичного простого числа
скорее всего сделает {Р — 1)-метод Полларда бесполезным.

8.2.4. Разность квадратов
Основной прием в алгоритмах факторизации, известный уже много
веков, заключается в генерировании двух целых чисел х иу прибли­
зительно той же величины, что и iV, удовлетворяющих условию
ж^ = у^ (modAT).
Применяя формулу сокраш;енного умножения, получим
х^ -у^ = {х- у){х -h у) = О (modiV).
Если N = р ^ q^ то имеют место четыре возможности:
1) р делит X — у^ и q делит х -\-у;
2) р делит X + у^ VL q делит х — у\
3) как р, так и q делят х — у, но не делят ж + у,
4) как р, так и q делят ж + у, но не делят х — у.
8.S. Современные методы факторизации

Эти случаи встречаются с равной вероятностью, а именно 1/4. Если
мы теперь вычислим
d= nOJ\{x-y,N),
ТО в зависимости от ситуации может получиться одно из четырех:
l)d = p, 2)d = q, 3)d = N, 4)d=l.
Поскольку эти равенства равновероятны, с вероятностью 1/2 мы
найдем нетривиальный делитель числа N, Остается только понять,
как же подобрать подходящие х и у^ разность квадратов которых
делится на N.


8.3. Современные методы факторизации
Современные методы разложения чисел на множители построены
на следующей стратегии, основанной на разности квадратов, о чем
мы с Вами только что говорили.
- Выбирают границу гладкости В,
- Вычисляют базу простых чисел ^ не превосходящих В (или
факторбазу F ) .
- Находят большое количество пар Б-гладких чисел ж и у, удо­
влетворяющих условию X = у (modTV). Такие пары называют
соотношениями на факторбазе.
- С помощью линейной алгебры по модулю 2 ищут комбинацию
соотношений, которая дает X и У с условием Х^ = Y^ (modTV).
- Пытаются найти делитель 7V, вычисляя НОД {X — У, N),
Самое трудное во всех алгоритмах, использующих такую страте­
гию, — это поиск соотношений. Указанная стратегия может приме­
няться и для дискретного логарифмирования, о чем мы упоминали в
предыдущей главе. Здесь мы расскажем о тех частях, которые явля­
ются общими А^ля всех алгоритмов, разлагающих на множители, и
объясним, почему они работают.
Один из подходов к факторизации основан на теории конеч­
ных групп. Мы уже говорили, что информация о порядке группы

<< Предыдущая

стр. 33
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>