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

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

ОГЛАВЛЕНИЕ

Следующая >>

(Z/iVZ)* эквивалентна разложению числа N на множители. Поэтому
можно сказать, что задача факторизации сводится к определению
порядка группы. Факторбаза, по существу, является множеством
образующих группы (Z/JVZ)*, в то время как соотношения — суть
соотношения между этими образующими. Как только достаточно
большое количество соотношений между образующими будет най­
дено, с помощью стандартных алгоритмов теории групп можно бу-
Глава 8. Тесты на простоту и факторизация

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

8.3.1. Комбинирование соотношений
Алгоритм приведения матрицы к нормальной форме Смита слиш­
ком сложен р^ля тех алгоритмов факторизации, в которых использу­
ются более элементарные методы линейной алгебры, что мы сейчас
и собираемся продемонстрировать. Предположим, что у нас есть
такие соотношения:
pVr^zzzjr^V^^ (modTV),
pq^r^ = pqr^ (modTV),
p^q^r^ =pq^r'^ (modN),
где p^ q и r — простые числа из нашей факторбазы F. Разделив
левую часть каждого из равенств на правую, получим
p-^qr˜^ =1 (modN),
^ V = l (modTV), (8.1)
p'^q'^r = 1 (mod TV).
Перемножая последние два соотношения, находим
(mod TV).
PV^^ = 1

Следовательно, если X = pq^r^^ а У = 1, то
Х2 = у2 (modTV),
и мы можем с вероятностью пятьдесят процентов найти делитель,
вычисляя ПОД {X - У, TV).
В этом примере легко усмотреть необходимые преобразования,
позволяющие получить разность квадратов, делящуюся на TV. На
практике факторбаза может состоять из сотен тысяч простых чи­
сел, и мы можем найти примерно такое же количество соотношений.
Поэтому необходимо как-то автоматизировать процесс комбиниро­
вания соотношений для получения требуемой разности квадратов.
В этом нам помогает линейная алгебра.
Объясним применение методов линейной алгебры на предыду­
щем простом примере. Напомним, что соотношения в нем эквива-
8.3. Современные методы факторизации

лентны соотношениям (8.1). Чтобы определить, какие из них стоит
перемножить и получить полный квадрат, выписывают матрицу А,
столбцы которой соответствуют простым числам, участвуюш;им в
соотношениях (р, ^, г в нашем случае), а строки — уравнениям. При
этом от каждого уравнения берутся только показатели простых чи­
сел, причем по модулю 2. В нашем примере матрица имеет вид:
/ -1 1 -1 \ / -1 1 1\
А= (mod 2).
0 2 3 ОО1
\22 ly \00iy
Найдем теперь такой двоичный вектор Z, что ZA = О (mod 2). В на­
шем примере искомый вектор — Z = (О 1 1). Действительно,


= (0 0 0) (mod 2).


Вектор Z говорит нам, что умножая друг на друга два последних
соотношения, мы получим полный квадрат по модулю N.
Поиск вектора Z можно осуществить с помош;ью некоторого ва­
рианта элементарных преобразований Гаусса. Как правило, в об­
щей ситуации нам необходимо иметь больше уравнений (т. е. соот­
ношений), чем элементов базы множителей. Комбинирование соот­
ношений в целях поиска полного квадрата — обычно самая труд­
ная часть алгоритмов факторизации, поскольку соответствующие
матрицы имеют очень большие размеры. Например, при примене­
нии квадратичного решета в числовом поле к факторизации сто-
значного десятичного числа может потребоваться матрица с более
чем 100 000 строками и столбцами. В результате создаются большие
проблемы с распределением компьютерной памяти, которые пыта­
ются обойти, создавая специальные программы обработки матриц
или специализированные суперкомпьютеры.
Матрицы, появляющиеся при разложении интересных для кри­
птографии чисел, имеют порядка 500 000 строк и столько же столб­
цов. Поскольку матрицы двоичные, А^ЛЯ записи каждого элемента
достаточно одного бита. Если бы у нас были плотно заполненные
матрицы, то для ее записи в компьютер нам бы потребовалось около
29 гигабайт. К счастью, матрицы очень сильно разрежены, поэтому
места для их хранения требуется не слишком много.
Как мы говорили выше, вектор Z, аннулирующий матрицу, мож­
но искать, применяя разновидность элементарных преобразований
Глава 8, Тесты на простоту и факторизация

Гаусса над полем Z/2Z. Стандартный метод Гаусса преобразует ма­
трицу к верхнетреугольному виду, который может оказаться плот­
ным. Так что применяя его, мы опять приходим к проблеме памяти.
Для преодоления возникающей трудности развиты довольно хоро­
шие матричные алгоритмы, которые стараются не менять матрицу
вообще. Мы не будем их здесь обсуждать, а отошлем интересую­
щихся к книге Ленстры и Ленстры, на которую есть точная ссылка
в разделе «Дополнительная литература».
Мы еще не рассказали о том, как найти соотношения. Этому как
раз и посвящен следующий параграф.


8.4. Метод решета в числовом поле
Квадратичное решето в числовом поле — самый быстрый из из­
вестных алгоритмов разложения на множители. Основная его идея
состоит в поиске целых чисел х и у^ разность квадратов которых
делится на N. Как уже было сказано, после этого можно надеяться,
что НОД {х — y^N) — нетривиальный делитель числа 7V.
Чтобы объяснить работу этого метода, мы начнем с линейно­
го решета и покажем, как оно может быть обобщено до решета в
числовом поле. Линейное решето — не очень хороший алгоритм,
на котором, однако, демонстрируются основные идеи эффективных
алгоритмов.

8.4.1. Л и н е й н о е репхето
Предположим, что мы собираемся разложить на множители 5-глад-
кое число N с некоторой границей В, Для этого надо сформировать
факторбазу «малых» простых чисел
F = {p\p^ В}.
Идея линейного решета состоит в поиске таких чисел а и Л, д^ля
которых комбинация b = a + NX является В-гладкой. Причем а тоже
нужно выбирать среди S-гладких чисел. Тогда будут иметь место
разложения


peF peF
из которых получаются следующие соотношения на факторбазе:
JJp«p = J J / p (modTV).
peF peF
8,4- Метод решета в числовом поле 225

Таким образом, основной вопрос линейного решета звучит так: как
найти нужные значения а и А? Их поиск осуш;ествляют по следую-
П1;ей схеме:
- фиксируют произвольное значение А;
- заводят просеивающий массив с А-\- 1 нулевыми элементами,
пронумерованными от О до А;
- для каждого простого числа р Е F прибавляют log2P к ка­
ждому значению ячейки массива, чей номер сравним с —XN
по модулю р]
- выбирают а как номер ячейки, значение которой превышает
определенную пороговую величину, например, является мак­
симальным элементом массива.
Дело в том, что при удачном выборе пороговой величины взятый
номер ячейки, будучи сложенным с A7V, имеет хорошие шансы ока­
заться ^-гладким и, одновременно, делиться на большое количество
простых чисел из F.
Разберем пример. Пусть N = 1159 и F = {2,3,5, 7,11}. Выберем
А = — 2. Наша цель — найти гладкое число вида а — 2N. Вводим
массив:
0 1 2 3 4 5 6 7 8 9
0,0 0,0 0,0 0,0 0,0 0,0 0,0 0,0 0,0 0,0
Берем первое простое число из F , а именно, р = 2, и вычисляем
—XN (modp) = 0. Прибавляем теперь log2 2 = 1 к содержимому
ячеек с четными номерами.

0 1 2 3 4 5 6 7 8 9
1,0 0,0 1,0 0,0 1,0 0,0 1,0 0,0 1,0 0,0
Переходим к р = 3 и находим —XN (mod3) = 2. Добавляем log2 3 =
= 1,6 к ячейкам с номерами, равными 2 по модулю 3:

0 1 2 3 4 5 6 7 8 9
1,0 0,0 2,6 0,0 1,0 1,6 1,0 0,0 2,6 0,0
Продолжая процесс А,ЛЯ простых р = 5, 7 и 11, заполняем массив
полностью:
0 1 2 3 4 5 6 7 8 9
1,0 2,8 2,6 2,3 1,0 1,6 1,0 0,0 11,2 0,0
Глава 8, Тесты на простоту и факторизация

Содержимое восьмой ячейки максимально. Поэтому мы подозрева­
ем, что значению а = 8 соответствует гладкое и подходящее для
наших целей число, в чем несложно убедиться, поскольку
b = a-\N = ^-2-1159 = -2310 = - 2 • 3 • 5 • 7 • 11.
Итак, с помощью линейного решета мы получим большую кол­
лекцию чисел а и 6, удовлетворяющих соотношениям вида

аг = П ^ ' = П ^ ? ' ' = ^^ (modiV).
PjeF pjeF

Имея по крайней мере | 5 | + 1 таких соотношений, можно сформи­
ровать матрицу со строками
(а^д,..., ац, Ьг,ь • • •, bi^t) (mod2).
Затем найдем аннулирующий эту матрицу вектор Z, который под­
скажет, как перемножить соотношения, чтобы получить равенство
вида
х'^ = у^ (modAT).
Используя его, можно попытаться найти делитель числа N, Если
попытка окажется неудачной, нужно найти новый аннулирующий
вектор и сформировать другую разность квадратов.
Основной вариант линейного решета дает слишком бедный уро­
жай соотношений. Существует его разновидность, называемая ва­
риацией больших простых чисел, которая ослабляет условия линей­
ного решета, позволяя парам а и b быть почти 5-гладкими, допус­
кая по одному «большому» простому делителю этих чисел. При этом
«большие» простые числа комбинируются таким образом, что аппа­
рат линейной алгебры, привлекаемый к линейному решету, работает
без изменения. Это делается с помощью построения графов и алго­
ритмов, вычисляющих базисы в множестве циклов графа. Вариация
больших простых чисел появилась в квадратичном решете, но ра­
ботает в любых просеивающих алгоритмах, раскладывающих числа
на множители.
Ясно, что просеивание-можно осуществлять параллельно. По­
этому такой алгоритм можно распределить между большим числом
компьютеров по всему миру. Подчиненные компьютеры сообщают
все найденные ими соотношения на главный сервер, который осуще­
ствляет заключительную стадию алгоритма, связанную с линейной
алгеброй. Таким образом Интернет можно превратить в «один боль­
шой» вычислительный центр, занимающийся задачей факторизации.
Заключительный этап с линейной алгеброй, как мы уже отмечали.
8,4- Метод решета в числовом поле

часто требует специального оснаш;ения и большого объема памяти.
Поэтому последний этап невозможно распределить между дочерни­
ми компьютерами.

8.4.2. Рехпето в числовом поле

Линейное решето — простейший, но не слишком хороший метод
факторизации больших чисел. И действительно, линейное решето
никогда не предлагалось как практический алгоритм разложения на
множители. Однако его работа поучительна для восприятия других
просеиваюш;их алгоритмов. Решето в числовом поле использует для
построения соотношений между элементами факторбазы арифме­
тику конечных полей. Собственно, это единственная модификация
по сравнению с линейным решетом. Этап линейной алгебры, вариа­
ция больших простых чисел и распределение задачи между разными
компьютерами, — все остается практически без изменения в алго­
ритме решета в числовом поле. Расскажем теперь об этом алгорит­
ме, но в существенно более простой его форме, чем используемая в
реальной жизни. Читатель, незнакомый с алгебраической теорией
чисел, может пропустить этот параграф.
Сначала строят нормированные неприводимые многочлены / i и
/2 степеней di и ^2 с целыми коэффициентами, удовлетворяющие
условию
/i(m) = /2(m) = 0(modiV)

для некоторого m G Z. Алгоритм пользуется арифметикой числовых
полей
Ki=Q{ei) и K2 = Q{e2),
где /i(^i) = /2(^2) = 0. Зафиксируем обозначения для двух гомо­
морфизмов
Г Z[ei] Z/ATZ,
[^ Ui \-^ т.

Как и в линейном решете, мы стремимся найти множество
Sc{{a,b)eZ^\ Н0Д(а,6) = 1}
таких элементов, что

П ( а - 6 0 1 ) = ^2 и Д (а-6^2) = 7 ' ,
{a,b)eS ia,b)eS
228 Глава 8. Тесты на простоту и факторизация

где ^ G iiTi, а 7 ^ ^ 2 - Вычислив ^ и 7? получим
^i{P? = ^2{l? (modiV)
и можно надеяться, что число
HOД(iV•,vPl(;б)-<^2(7))
является нетривиальным делителем N.
В связи с этим можно сформулировать три очевидные задачи.
- Как найти множество S1
- Как вычислить /3 по известному элементу ^^ G Q(^i)?
- Как подобрать многочлены / i и /2 из первой части алгоритма?

8.4.3. К а к н а й т и множ:ество S1
Аналогично процессу в линейном решете, с помощью линейной ал­
гебры мы строим множество S так, чтобы разности
а — Ъвх и а — Ьв2
были «гладкими». Необходимо уточнить, что в данной ситуации на­
зывать гладкими объектами. Для этого придется привлечь теорию

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

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

ОГЛАВЛЕНИЕ

Следующая >>