Вычислительно сложные задачи теории чисел

Серия
Суперкомпьютерное 
Образование

Координационный совет
Системы научно-образовательных центров
суперкомпьютерных технологий

Председатель Координационного совета

В. А.  Садовничий,
ректор МГУ имени М. В.  Ломоносова,
академик

Заместители председателя совета

Е. И.  Моисеев,
декан факультета вычислительной математики и кибернетики
МГУ имени М. В.  Ломоносова, 
академик

А. В.  Тихонравов,
директор Научно-исследовательского вычислительного центра
МГУ имени М. В.  Ломоносова, 
профессор

Члены совета

В. Н. Васильев, ректор Санкт-Пе тер  бургского национального исследовательского госу дар ственного университета инфор ма ционных технологий, механики 
и оптики, чл.-корр. РАН, профессор; В. Г. Захаревич, ректор Южного федерального университета, профессор; Н. Н. Кудрявцев, ректор Московского физико-технического института, чл.-корр. РАН, профессор; Г. В. Майер, 
ректор национального исследовательско го Томско го государственного университета, профессор; А. А. Фаткулин, проректор по науке и инновациям 
Дальневосточного федерального университета, профессор; Е. В. Чупрунов, 
ректор националь ного исследовательского Ниже городского го су дарственного 
университета, про фессор; А. Л. Шестаков, ректор национального исследовательского Южно- Уральского государственного университета, профессор; 
В. Н. Чубариков, декан механико-математического факультета МГУ имени 
М. В. Ломоносова, профессор; М. И. Панасюк, директор Научно-ис сле дова тельского института ядерной физики МГУ имени М. В.  Ломоно сова, профессор; Вл. В. Воеводин, заме ститель директора Научно-исследо ва тель ского 
вычислительного центра МГУ имени М. В.  Ломоносова, исполнительный директор 
НОЦ «СКТ-Центр», член-корреспондент РАН.

Вычислительно сложные 
задачи теории чисел

Е. А. Гречников, С. В. Михайлов, 
Ю. В. Нестеренко, И. А. Поповян

Московский государственный университет
имени М. В. Ломоносова

Допущено УМО по классическому университетскому образованию 
в качестве учебного пособия для студентов высших учебных заведений, 
обучающихся по направлениям ВПО 
010400 «Прикладная математика и информатика» 
и 010300 «Фундаментальная информатика 
и информационные технологии»

Издательство Московского университета
2012

УДК 007 (075) 
ББК 32.973.2
В92

© Коллектив авторов, 2012 
© Издательство Московского университета, 2012
ISBN 978-5-211-06342-6

Вычислительно сложные задачи теории чисел: Учеб. пособие / 
Е. А. Гречников, С. В. Михайлов, Ю. В. Нестеренко, И. А. Поповян. – М.: 
Издательство Московского университета, 2012. – 312 с. – (Серия «Суперкомпьютерное образование»)
ISBN 978-5-211-06342-6

В92

В учебном пособии подробно рассматриваются четыре задачи, привлекающие 
внимание исследователей на протяжении последних десятилетий: разложение больших составных чисел на множители, дискретное логарифмирование в мультипликативной группе вычетов по простому модулю, решение больших разреженных систем 
линейных уравнений над конечными полями, вычисление ранга эллиптических 
кривых, определенных над полем рациональных чисел. 
Наиболее быстрые алгоритмы решения первых двух задач основаны на так называемом алгоритме решета числового поля, сводящем их к решению больших разреженных систем линейных уравнений над конечными полями. Системы эти настолько велики, что к ним не применимы обычные алгоритмы решения. Используются 
специальные блочные итерационные алгоритмы. 
Эта область прикладной теории чисел активно развивается во всем мире в связи с приложениями в криптографии. Из-за отсутствия нижних оценок сложности 
решения этих теоретико-числовых задач, единственным способом проверки надежности используемых криптографических алгоритмов служит их практическая проверка с использованием самых совершенных алгоритмов и наиболее мощной вычислительной техники.
Ключевые слова: факторизация, дискретное логарифмирование, разреженные линейные системы уравнений, ранг эллиптической кривой.
УДК 007 (075) 
ББК 32.973.2

Уважаемый читатель!

Вы держите в руках одну из книг серии «Суперкомпьютерное образование», выпущенную в рамках реализации проекта комиссии Президента РФ по модернизации и технологическому развитию экономики России «Со здание системы подготовки высококвалифицированных 
кадров в области суперкомпьютерных технологий и специализированного программного обеспечения». Инициатором издания выступил 
Суперкомпью терный консорциум университетов России.
Серия включает более 20 учебников и учебных пособий, подготовленных ведущими отечественными специалистами в области суперкомпьютерных технологий. В книгах представлен ценный опыт преподавания супер компьютерных технологий в таких авторитетных 
вузах России, как МГУ, ННГУ, ТГУ, ЮУрГУ, СПбГУ ИТМО и многих 
других. При подготовке изданий были учтены рекомендации, сформулированные в Своде знаний и умений в области суперкомпьютерных 
технологий, подготовленном группой экспертов Суперкомпьютерного 
консорциума, а также международный опыт.
Современный уровень развития вычислительной техники и методов математического моделирования дает уникальную возможность 
для перевода промышленного производства и научных исследований 
на качественно новый этап. Эффективность такого перехода напрямую 
зависит от наличия достаточного числа высококвалифицированных 
специалистов. Данная серия книг предназначена для широкого круга 
студентов, аспирантов и специалистов, желающих изучить и практически использовать параллельные компьютерные системы для решения трудоемких вычислительных задач.
Издание серии «Суперкомпьютерное образование» наглядно демон ст рирует тот вклад, который внесли участники Суперкомпьютерного консорциума университетов России в создание национальной 
системы под готовки высококвалифицированных кадров в области 

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

Ректор Московского университета,
Президент Суперкомпьютерного консорциума университетов России,
академик РАН  В. А. Садовничий

ОГЛАВЛЕНИЕ

Предисловие . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
11

Часть I. Решение линейных систем уравнений

Введение . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
14

Глава 1. Скалярные алгоритмы и приближения Паде . .. .. .. .. .. .. .. .. .. .. .. .
17
1.1. Приближения Паде . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
17
1.1.1. Алгоритм Евклида . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
19
1.1.2. Подходящие дроби как решения систем
линейных уравнений . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
21
1.1.3. Промежуточные дроби . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
23
1.1.4. Алгоритм Берлекемпа – Месси . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
26
1.2. Алгоритм Видемана . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
29
1.2.1. Алгоритм Видемана и приближения Паде . .. .. .. .. .. .. .. .. .
29
1.3. Алгоритм Ланцоша . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
31
1.3.1. Алгоритм Ланцоша и приближения Паде. .. .. .. .. .. .. .. .. .. .
35
1.3.2. Схема Горнера и ортогональные многочлены . .. .. .. .. .. .. .
43

Глава 2. Блочный алгоритм Видемана – Копперсмита. .. .. .. .. .. .. .. .. .. .. .. .
51
2.1. Описание алгоритма . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
51
2.2. Построение матричных приближений Паде. .. .. .. .. .. .. .. .. .. .. .. .. .
53
2.2.1. Приведенный базис . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
57
2.2.2. Сдвиг степеней . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
62
2.3. Вероятность получения ненулевого решения. .. .. .. .. .. .. .. .. .. .. .. .
64
2.3.1. Обзор многомерного случая. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
65
2.3.2. Одномерный случай . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
68

Глава 3. Параллельные алгоритмы Видемана и Ланцоша . .. .. .. .. .. .. .. .. .
76
3.1. Краткое описание алгоритмов. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
76
3.1.1. Алгоритм Видемана . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
76

Оглавление

3.1.2. Алгоритм Ланцоша . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
77
3.1.3. Блочные алгоритмы над полем GF(2) . .. .. .. .. .. .. .. .. .. .. .. .
78
3.1.4. Вычислительные вопросы . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
79
3.2. Последовательные версии алгоритмов. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
80
3.2.1. Алгоритмы Видемана . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
80
3.2.2. Алгоритмы Ланцоша. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
82
3.3. Параллельные версии алгоритмов. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
84
3.3.1. Параллельное умножение матрицы на вектор. .. .. .. .. .. .. .
85
3.3.2. Параллельный алгоритм Видемана . .. .. .. .. .. .. .. .. .. .. .. .. .. .
94
3.3.3. Параллельный алгоритм Ланцоша . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
96
3.4. Некоторые замечания. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
97

Часть II. Алгоритм просеивания и его применения

Введение . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 100

Глава 1. Разложение на множители больших чисел . .. .. .. .. .. .. .. .. .. .. .. .. .. . 102
1.1. Алгоритм факторизации методом решета числвого поля . .. .. . 102
1.2. Порядок A и его свойства . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 105
1.2.1. Простые идеалы первой степени в кольце A . .. .. .. .. .. .. . 109
1.2.2. Показатели . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 111
1.2.3. Расширение идеалов кольца A. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 118
1.3. Оценка индекса порядка A. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 122
1.4. Обоснование алгоритма . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 132
1.5. Извлечение квадратного корня в поле алгебраических чисел
135

Глава 2. Алгоритм дискретного логарифмирования . .. .. .. .. .. .. .. .. .. .. .. .. .. . 142
2.1. λ-функции и виртуальные логарифмы. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 143
2.1.1. λ-функции . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 143
2.1.2. Чистая образующая главного идеала . .. .. .. .. .. .. .. .. .. .. .. .. . 145
2.1.3. Определение виртуального логарифма идеала . .. .. .. .. .. . 147
2.1.4. Основная теорема . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 148
2.2. Алгоритм дискретного логарифмирования методом решета
числового поля . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 152
2.3. Комментарии и обоснование алгоритма. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 157
2.3.1. Разложение простых чисел в произведение
простых идеалов . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 157
2.3.2. Уравнения системы . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 158
2.3.3. Вычисление индивидуальных логарифмов . .. .. .. .. .. .. .. .. . 159

8

Оглавление

Глава 3. Просеивание . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 164
3.1. Просеивание на решетках . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 164

Глава 4. Выбор многочленов . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 171
4.1. Характеристики многочленов . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 173
4.1.1. Размер многочлена . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 173
4.1.2. Гладкость многочлена . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 174
4.1.3. Фунции Мерфи E и e . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 177
4.2. Классические алгоритмы . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 178
4.2.1. Разложение по основанию m. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 178
4.2.2. Алгоритм Монтгомери . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 179
4.3. Современные алгоритмы . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 181
4.3.1. Алгоритм Монтгомери – Мерфи . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 181
4.3.2. Алгоритм Кляйнюнга . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 183
4.3.3. Оптимизация многочленов . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 189

Часть III. Эллиптические кривые над полем
рациональных чисел

Введение . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 193

Глава 1. Рациональные точки на эллиптических кривых . .. .. .. .. .. .. .. .. . 196
1.1. Основные определения. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 196
1.2. Точки кручения . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 199
1.3. Высоты и их свойства . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 211
1.4. Редукция по простому модулю . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 218

Глава 2. Нахождение ранга эллиптической кривой . .. .. .. .. .. .. .. .. .. .. .. .. .. . 222
2.1. Алгоритм Берча – Суиннертон-Дайера
и его обоснование . . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 222
2.2. Реализация алгоритма Берча – Суиннертона-Дайера . .. .. .. .. . 232
2.2.1. Отыскание 2-накрытий . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 232
2.2.2. Отбор неэквивалентных 2-накрытий . .. .. .. .. .. .. .. .. .. .. .. .. . 232
2.2.3. Поиск p-адических точек на 2-накрытиях . .. .. .. .. .. .. .. .. . 235
2.2.4. Поиск рациональных точек на 2-накрытиях
и эллиптических кривых. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 237

Глава 3. Построение базиса группы рациональных точек . .. .. .. .. .. .. .. .. . 242
3.1. Общая схема алгоритма . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 242

9

Оглавление

3.2. Нахождение высот рациональных точек . .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 243
3.2.1. Разложение канонической высоты
в сумму локальных высот . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 243
3.2.2. Вычисление локальной высоты в архимедовом случае
246
3.2.3. Замена параметра . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 248
3.2.4. Оценка ошибки при вычислении локальной высоты . .. . 253
3.2.5. Вычисление локальной высоты в неархимедовом случае 257
3.3. Работа с 2-накрытиями . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 259
3.4. Факторгруппа E(Q)/2E(Q) . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 261
3.5. Оценка нижней границы высот рациональных точек. .. .. .. . .. . 263
3.5.1. Вычисление эллиптических логарифмов. .. .. .. .. .. .. .. .. .. .. . 264
3.5.2. Вычисление суммы DE(n). .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 274
3.5.3. Вычисление константы α. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 277
3.5.4. Основной алгоритм . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 280
3.6. Выделение базиса из полного набора независимых точек . .. . 283
3.7. Поиск рациональных корней многочленов. .. .. .. .. .. .. .. .. .. .. .. .. .. . 288

Глава 4. Задача дискретного логарифмирования
на эллиптической кривой . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 291

Введение . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 291
4.1. Обзор некоторых методов. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 292
4.2. Исчисление “xedni” . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 297
Список литературы . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 303

10

Предисловие

Вычислительные задачи теории чисел в течение столетий привлекали
внимание ученых. Сначала многие вычисления выполнялись вручную с
огромными затратами времени и сил. При этом было придумано множество остроумных алгоритмов и приемов, позволивших найти путь
решения, менее затратный с точки зрения времени вычислений. Например, П. Ферма доказал, что при любом целом a > 0, не являющимся
квадратом, уравнение x2 − ay2 = 1 имеет бесконечно много решений в
целых числах (x, y), и нашел алгоритм, позволяющий вычислять последовательно эти решения. Так он установил, что наименьшее решение уравнения x2 − 109y2 = 1 есть x = 158070671986249, y = 15140424455100.
А Л. Эйлер опроверг одну из гипотез Ферма, доказав, что число 232 + 1
не является простым. Он разложил это число на множители, проверив
его делимость на 641.
Появление компьютеров по-новому осветило эту область науки. Решения многих задач, требовавшие большого объема вычислений, стали доступными. Например, стало возможным строить простые числа,
записываемые тысячами десятичных знаков, вычислять более 2 · 1012

знаков после запятой в десятичном разложении числа π, проверить, что
первые 1013 нетривиальных нулей дзета-функции Римана ζ(s) лежат в

комплексной плоскости на прямой Re s = 1

2, найти полные множества
решений ряда диофантовых уравнений и т.д. Появление вычислительной
техники стимулировало теоретические исследования. Был придуман полиномиальный по затратам времени алгоритм проверки целых чисел на
простоту, был найден также полиномиальный алгоритм разложения на
множители многочленов с целыми коэффициентами.
В то же время некоторые вычислительные задачи сохранили свою
сложность. Такой является, например, задача разложения составного
целого числа на множители. Конечно, с помощью мощного компьютера можно сравнительно быстро разложить на множители целое число,
записываемое сотней десятичных знаков. Тогда как составное число,
записываемое 300-ми десятичных знаков и выбранное более или менее

11

Предисловие

случайно, в настоящее время никто, даже с использованием самых мощных суперкомпьютеров и за год непрерывных вычислений, скорее всего,
разложить на множители не сможет. Быстрые алгоритмы для решения
этой задачи на данный момент не известны. Увеличение длины входных
данных в несколько раз ведет к почти экспоненциальному увеличению
времени вычислений. Подобные трудные в вычислительном отношении
задачи – для их решения известны лишь экспоненциальные или субэкспоненциальные алгоритмы – находят применение в криптографии, где
служат основой некоторых важных алгоритмов шифрования.
Эта книга посвящена трудным вычислительным задачам теории чисел.
Мы подробно рассмотрим здесь три задачи, привлекавшие внимание
исследователей на протяжении десятилетий.
• Разложение составных чисел на множители (факторизация целых
чисел).
• Дискретное логарифмирование в мультипликативной группе вычетов
по простому модулю.
• Вычисление ранга эллиптических кривых, определенных над полем
рациональных чисел и базиса группы рациональных точек.
Наиболее эффективные в настоящее время методы решения первых
двух задач используют так называемые алгоритмы просеивания (алгоритмы решета) и сводят эти задачи к решению больших разреженных систем
линейных уравнений над конечными полями. Вопросам, связанным с
решением таких систем, посвящена отдельная часть книги.
Книга состоит из трех частей, каждая из них имеет краткое введение,
с более подробным описанием ее содержания. Для понимания книги
достаточны знания курсов элементарной теории чисел, начал теории
алгебраических чисел, а также стандартных курсов алгебры и анализа в
объеме первых двух годов обучения. Изложение предполагает знакомство
читателя с общими принципами программирования параллельных алгоритмов.
Мы хотели бы высказать слова благодарности нашим коллегам
О. Н. Герману и Е. А. Уланскому за участие в обсуждении и подготовке
отдельных мест книги.

12

Часть I 

РЕШЕНИЕ ЛИНЕЙНЫХ 
СИСТЕМ УРАВНЕНИЙ

Введение

Большие системы линейных уравнений над конечными полями, методы решения которых мы рассматриваем в этой части книги, возникают в
таких вычислительно сложных задачах теории чисел, как факторизация,
то есть разложение целых чисел в произведение простых сомножителей,
и дискретное логарифмирование в конечных полях. Общий подход, позволяющий свести задачи факторизации и дискретного логарифмирования
к решению линейных систем над конечными полями, получил название
методов решета (sieving). Наиболее популярным и эффективным на настоящий момент примером таких методов является решето в числовом
поле (или решето числового поля, number field sieve, NFS).
Конкретные методы решета модифицируются в зависимости от вида задачи и ее особенностей и в общем случае приводят к линейным
системам над различными конечными полями. С точки зрения выбора
алгоритмов решения линейных систем все поля можно разделить на две
группы: к первой группе относятся поля с достаточно большим количеством элементов, а ко второй – остальные поля. Для полей с большим числом элементов можно доказать, что все рассматриваемые далее
методы дают решение линейных систем с высокой вероятностью. В то
же время применение методов решения линейных систем над конечными
полями с небольшим числом элементов, например, над GF(2), требует
использования усложненных алгоритмов.
Рассматриваемые нами системы, кроме того, что они являются большими, к тому же – разреженные. Среднее число элементов в строке
матрицы составляет порядка 102 при типичных размерах от 106 до 108.
Традиционные методы исключения для решения таких систем не могут
применяться, поскольку резкое возрастание числа ненулевых элементов в
процессе исключения приводит к быстрому расходу памяти. В результате
особый интерес вызвали итерационные методы, в которых матрица линей
14