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

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

ОГЛАВЛЕНИЕ

Следующая >>

числовых полей. Обобщая старое определение гладких целых чисел
на случай алгебраических целых, мы получаем следующее определение:

Определение 8.5. Алгебраическое целое число называют «глад­
ким»^ если и только если идеал, им порожденный, делится только на
«маленькие» простые идеалы.
Положим по определению: Fi{X,Y) = ?^^/г{у). Тогда
- bOi) = Fi{a,b).
^Q№)/Q(^

Мы определим две факторбазы, по одной для каждого многочлена:
^г — {(^5^)1 Р — простое, г ЕЪ^ причем /г(г) = О (modp)}.
Каждый элемент факторбазы !Fi соответствует степени простого
идеала в подкольце Ъ[вг] целых элементов 0Q(^i) поля ^{вг). Идеал
имеет вид
(^А-г)=рЪЩЛ-{вг-г)Ъ[вг].
Для данных значений а и Ь мы можем легко определить, «расклады­
вается» ли идеал (а — вф) над нашей фактор баз ой. Обратите вни­
мание на то, что слово «раскладывается» взято в кавычки. Дело в
том, что теорема о единственности разложения на простые множи­
тели неверна в кольце Щвг]^ а справедлива лишь в кольце целых,
8,4- Метод решета в числовом поле

т.е. в Oq(^0.y Тем не менее, отсутствие однозначности разложения
не препятствует нашим целям. Чтобы убедиться в этом, достаточно
обратиться к книге Ленстры и Ленстры.
Если Z[ei] = (^Qidi)') то сформулированный ниже порядок дей­
ствий дает действительно единственное разложение идеала (а — вф)
в произведение простых.
- Положим
Fi{a,b)= П 4''

- Если идеал, соответствующей паре (р, г), нетривиальным обра­
зом входит в разложение элемента а — вф^ то возникает равен­
ство (а : Ь) = (г : 1) (modp) элементов проективной прямой
над полем Fp.
- Получаем

{Pj,r)eTi

Эта процедура подводит нас к алгоритму, просеиваюш;ему элементы
а и Ь, А,ля которых идеал {а — вф) раскладывается над факторбазой.
Как и в случае линейного решета, просеивание позволяет избегать
большого количества дорогостояш;их попыток деления в надежде
определить гладкие идеалы. Нам остается только проверить разло­
жимость элементов, вероятность разложения которых достаточно
большая.
- Фиксируем а.
- Задаем просеиваюш;ий массив р,ля b {—В ^ b ^ В)^ заполняя
его по следуюш;ему правилу:
S[b] = \og2iFi{a,b)-F2{a,b)).

- Для каждой пары (р, г) Е Ti вычитаем log2 р из каждого эле­
мента массива с номером Ь, удовлетворяюш;его условию:
а — гЬ = О (modp).

- Числа Ь, которые нам нужны, соответствуют элементам 5[Ь],
лежаш;им ниже некоторого допустимого уровня.
Если уровень допуска установлен разумным образом, то с большой
долей вероятности Fi(a, b) и F2{a^ b) разложатся на простые идеалы
из факторбазы и, быть может, будут иметь в качестве множителей
Глава 8. Тесты на простоту и факторизация

по одному «большому» простому идеалу. Мы перепишем эти разло­
жения в виде соотношений, как уже делали в линейном решете.
Затем, после применения линейной алгебры, мы найдем искомое
подмножество S всех таких пар (а, Ь), что

п {а — 9ib) = квадрат идеала в Z[9i].
ia,b)eS
Однако это еще не все. Напомним, что мы хотели получить про­
изведение П ^ ˜ ^г^^ которое будет квадратом э л е м е н т а из Z[^i].
Чтобы обойти эту проблему, нам нужно добавить информацию из
«бесконечного числа» мест. Пусть q — такое рациональное простое
число (не лежаш;ее ни в ^ i , ни в ^2)? Д-^^ которого найдется Sq с
fii^q) = О (modg) и f[{sq) ф О (modд) для какого-нибудь из зна­
чений г = 1 или 2. Потребуем тогда дополнительного условия, а
именно.

п (-
где ( ^ J — символ Лежандра. Ввиду мультипликативности символа
Лежандра, мы можем подставить это дополнительное условие в на­
шу матрицу. Сделаем это для нескольких простых q. Поэтому мы
выберем некое множество простых рациональных q и добавим соот­
ветствующие символы в нашу матрицу как дополнительные столбцы
нулей и единиц в соответствии с правилом

'а — Ь8п\ I 1, ставим О,
если ' »—
I —1, ставим 1.
Найдя достаточно много соотношений, мы рассчитываем найти и
такое подмножество 5, что




8.4.4. К а к и з в л е к а т ь к в а д р а т н ы е корни?
Теперь нужно научиться извлекать квадратные корни из элементов
для восстановления /3 и 7 по известным 0^ и 7^- Покажем, как это
делается для /3. Квадрат задан в виде


^ = Е ''Я
^
7=0
8-4' Метод решета в числовом поле

где aj — очень большие целые числа. Нам необходимо найти цело­
численные решения bj уравнения
^1-1 \^ di-l




Способ его решения принадлежит Кувеню. Он сводится к вычисле­
нию квадратных корней по модулю большого количества очень и
очень больших простых чисел р. После этого применяется китай­
ская теорема об остатках с надеждой восстановить искомый корень.
Это наиболее простой для изучения метод, хотя суш;ествуют и более
продвинутые способы, такие, например, как способ Нгуена.

8.4.5. В ы б о р начальных м н о г о ч л е н о в
Эта часть метода решета в числовом поле на сегодняшний день
больше смахивает на черную магию. Мы требуем выполнения толь­
ко одного условия:
/ i M = /2(m)-0(mod7V),
хотя суш;ествуют веские эвристические аргументы в пользу выбора
многочленов с дополнительными свойствами:
- Многочлены обладают малыми коэффициентами.
- Многочлены имеют «много» веш;ественных корней. Заметим,
что случайный многочлен четной степени вообще не имеет ве­
щественных корней.
˜ / i и /2 имеют «много» корней по модулю нескольких малых
простых чисел.
- Группы Галуа многочленов fi должны быть небольшими.
Иногда приходится тратить несколько недель на поиск хорошей
пары многочленов перед тем, как запустить соответствующий ал­
горитм факторизации. Известно несколько стратегий, применяю­
щихся для их поиска. Как только несколько кандидатов на тре­
буемые многочлены найдено, проводится серия экспериментальных
просеиваний, чтобы отобрать наиболее удачную пару, выдающую
нам большее число соотношений. Только после такого отбора имеет
смысл приступать к реальной задаче факторизации.

8.4.6. П р и м е р
Я благодарен Ричарду Пинчу, позволившему мне включить в книгу
пример, о котором идет речь в этом разделе. Пример взят из его
232 Глава 8. Тесты на простоту и факторизация

записок лекционного курса в Кембридже, прочитанного в середине
1990-ых годов.
Предположим, мы хотим разложить на множители число N —
= 290^ + 1 = 84101. Возьмем fi{x) = х^ + 1 и /2(х) =х-290, а число
т = 290. Тогда
/i(m) = / 2 ( m ) - 0 ( m o d 7 V ) .
С одной стороны, у нас есть кольцо Z[i] целых^ элементов поля Q(i),
а с другой — стандартное кольцо целых чисел Z.
Мы получаем следующие разложения:

X у N{x — гу) множители х — ту множители
-38 ˜1 1445 (5)(172) 252 (22)(32)(7)
-22 -19 845 (5)(132) (5488) (2^)(7^)
Затем мы находим два разложения, которые являются настоящими
разложениями элементов, поскольку Z[i] — область с единственным
разложением на множители:
- 3 8 + г = - ( 2 + г)(4 - if, - 2 2 + 19г = - ( 2 + г)(3 - 2г)^.
Следовательно, после применения элементарных методов линейной
алгебры мы обретаем следующие «квадраты»:
(-38 + г)(-22 + 19г) - (2 + if{3 - 2if{4: - if = (31 - 12г)^
и
(-38 + m ) ( - 2 2 + 19 X m) - (2^)(3^)(7^) - 1176^.
Применяя отображение cpi к элементу 31 — 12г, находим
(pi{31 - 12г) = 31 - 12 X m = -3449.
Теперь
(-3449)^ = (^i(31 - 12г)^ - (/?i((31 - I2if) =
= (/?i((-38 + г)(-22 + 19г)) = (pi{-38 + i)ipi{-22 + 19г) =
= (-38 + m ) ( - 2 2 + 19 X ш) = 1176^ (modiV).
Далее вычисляем
ПОД (iV, -3449 + 1176) = 2273 и ПОД (АГ, -3449 - 1176) = 37.
Следовательно, 37 и 2273 — делители числа N = 8А101.


^Здесь i — мнимая единица, т.е. г^ = —1. — Прим. перев.
8^4' Метод решета в числовом поле 233

К р а т к о е с о д е р ж а н и е главы

- Простые числа встречаются довольно часто, а вероятность то­
го, что случайное п-битовое число будет простым, равна 1/п.
- Исследовать числа на простоту можно с помощью вероятност­
ных тестов, таких как тест Ферма или алгоритм Миллера-
Рабина. Недостаток теста Ферма заключается в том, что су­
ществуют составные числа, которые выдерживают этот тест
по всем возможным основаниям.
- Для обоснования простоты какого-либо числа применяются
алгоритмы доказательства простоты, требующие полиноми­
ального времени.
- Алгоритмы факторизации часто основаны на вычислении раз­
ности квадратов.
- Современные алгоритмы факторизации разбиваются на две
стадии. На первой из них подбирается коллекция соотноше­
ний на факторбазе с помощью процесса просеивания, кото­
рый можно осуществить, разделив задачу между множеством
компьютеров через Интернет. На второй — эти соотношения
подвергаются преобразованиям методами линейной алгебры
на большом центральном сервере. Для окончания факториза­
ции вычисляется разность квадратов.

Дополнительная литература
Стандартная книга по вычислительной теории чисел, содержагцая
многие алгоритмы факторизации и доказательства простоты, —
это книга Коэна. Произведение Бача и Шаллита — тоже хороший
источник тестов на простоту. Основная работа, освещающая метод
решета в числовом поле, принадлежит Ленстре и Ленстре.
Е. Bach and J. Shallit. Algorithmic Number Theory. Volume 1: Efficient
Algorithms. MIT Press, 1996.
H. Cohen. A Course in Computational Algebraic Number Theory. Springer-
Verlag, 1993.
A. Lenstra and H. Lenstra. The Development of the Number Field Sieve.
Springer-Verlag, 1993.

Контрольные вопросы
8.1.1. В каких случаях стоит использовать метод пробного деления
для тестирования чисел на простоту?
234 Глава 8. Тесты на простоту и факт,оризацил

8.1.2. Что такое тест Ферма и в чем его главный недостаток?

8.1.3. В чем состоит основное различие между алгоритмами, тести­
рующими числа на простоту (например, алгоритм Миллера-
Рабина) и доказывающими простоту (например, ЕССР)!

8.1.4. Что подразумевают под гладкими числами и как их исполь­
зуют при разложении на множители?

8.1.5. Опишите (Р — 1)-метод факторизации.

8.1.6. Почему наличие пары чисел ж и ?/ с условием х^ — у^ (modTV)
позволяет найти нетривиальный делитель числа N с вероят­
ностью 1/2?

8.1.7. Что понимают под просеиванием и почему его используют в
современных алгоритмах разложения?

Лабораторные работы
8.2.1. Реализуйте тесты Ферма и Миллера - Рабина, описанные в
тексте, и найдите с их помощью свидетелей делимости числа
21024 _ 3 .

8.2.2. Напишите программу р^ля {Р — 1)-метода факторизации. На­
сколько большие составные числа Ваша программа сможет
разложить на множители?

Упражнения
8.3.1. Покажите, что если составное число N выдерживает тест
Ферма по основанию а, но не проходит тест Миллера-Ра­
бина по тому же основанию, то мы можем разложить N на
множители.
В следующих трех задачах раскрывается еще один метод Пол-
ларда факторизации N = р • q^ называемый р-методом. Пусть
хо — 2, гГг+1 =^ xf -\-1 (modiV).

8.3.2. Покажите, что если найти два разных элемента последова­
тельности, удовлетворяющих условию xi = Xj (mod/?), то с
высокой вероятностью мы можем разложить N на множите­
ли, вычисляя
Y{OJ\{xi-Xj,N).
8.4- Метод решета в числовом поле

8.3.3. Найдите аргументы, подтверждающие, что мы обязатель­

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

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

ОГЛАВЛЕНИЕ

Следующая >>