Крэндалл Р., Померанс К. Простые числа:
Криптографические и вычислительные аспекты. Пер. с англ. №5

Оглавление

От редактора перевода

Книга американских математиков Р.Крэндалла и К.Померанса "Простые числа: вычислительные и криптографические аспекты" посвящена важному современному направлению теории чисел  – вычислительной (или алгоритмической) теории чисел. Данное направление стало интенсивно развиваться с 70-х  гг. XX в., после открытия асимметричных криптосистем Диффи–Хеллмана и RSA. Этому развитию во многом способствовал бурный прогресс в области вычислительной техники. Тем не менее, как неоднократно подчеркивают авторы, в этой книге мы находим идеи, восходящие к великим математикам прошлого  – к Ферма, Эйлеру, Гауссу, Чебышёву.

Книга охватывает следующую тематику:

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

Неудивительно, что на первом месте стоит классическая теория простых чисел  – как мы уже упоминали, многие идеи современных алгоритмов восходят к классикам. Кроме того, без фундаментальных результатов аналитической теории чисел, к которым относится, например, асимптотический закон распределения простых чисел, открытый Ж.Адамаром и Ш.Валле Пуссеном в 1896 г., по существу невозможно провести анализ сложности теоретико-числового алгоритма.

С другой стороны, умение вычислить теоретико-числовую величину или построить теоретико-числовой объект позволяет лучше понять, как они устроены. Это может помочь пониманию сути теоретического понятия и даже привести к новым открытиям. К примеру, Л.  Эйлер был, кстати, и непревзойденным вычислителем.

Авторы отмечают, что эта двойственность помогала им в работе над книгой. Объединившись, они представили оригинальный взгляд на вычислительные и криптографические аспекты теории чисел. Многие важнейшие теоретико-числовые алгоритмы, описанные в книге, созданы ее авторами. Для книги характерна идейная ясность, простота и "многоуровневость" изложения, благодаря которой читатель сможет пройти путь от самых основ теории до самых последних результатов и проблем. Книга содержит тексты всех представленных алгоритмов (их более 100) и конкретные примеры их работы.

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

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

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

Работа по переводу книги на русский язык была выполнена сотрудниками механико-математического факультета МГУ им.М.В.Ломоносова  – А.В.Бегунцем (гл.1, 3), Я.В.Вегнером (гл.2 (2.3–2.5), 9, Приложение), В.В.Кнотько (гл. 4, 5), С.Н.Преображенским (гл. 6, 7), И.С.Сергеевым (гл. 2 (2.1–2.2), 8).

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

Авторы включили в книгу обстоятельный список литературы на английском языке. Редактором перевода составлен дополнительный список литературы о  простых числах. Он приведен в конце книги.

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

Предисловие

На страницах этой книги мы постарались построить связующее звено (надеемся, что даже мост) между "теорией" и "практикой" в области простых чисел. Разумеется, речь идет о теории чисел и о вычислительной практике. Созданы великие книги, рассказывающие об абстрактных свойствах простых чисел, и каждый из нас обращается к ним как к любимой классике. Однако экспериментальная сторона этого вопроса относительно молода, ведь несмотря на небеспочвенные утверждения о том, что теория вычислительных машин и систем ни в коем случае не является новой (к настоящему времени в ней уже произошли четыре или пять "революций"), необходимо принять во внимание многовековую и даже тысячелетнюю историю теоретических исследований в области простых чисел. Поэтому мы полагаем, что для научных трудов, основанных одновременно на знаменитых классических методах и современных вычислительных подходах, все еще остается место.

Замысел и тематика этой книги

Книга сочетает по сути взаимно дополняющие области компетенции обоих авторов (Р.Крэндалл  – скорее компьютерщик, а К.Померанс  – скорее теоретик). Первые главы носят более теоретический характер, хотя в них и описано несколько явных алгоритмов, а алгоритмическая составляющая существенно возрастает по мере дальнейшего продвижения читателя вглубь книги. Как в теоретических, так и в вычислительных сторонах вопроса мы старались продемонстрировать наиболее современный взгляд на теорию чисел. Чего мы не делали  – это не стремились к обоснованию всех тонкостей каждой детали. Это не только потребовало бы гораздо большего объема книги, но, как мы указываем в начале первой главы, можно сказать, что ни один человеческий ум не в состоянии охватить полной картины знаний о простых числах. Видимо, и команда из двух исследователей тоже не может обладать таким всеведением, по крайней мере именно так обстоит дело с нашей парой. Своей задачей мы сочли обеспечение ссылок на огромное число источников, содержащих подробное описание тех аспектов, которых нам не удалось раскрыть в достаточном объеме. Кроме того, совершенно ясно, что к моменту выхода книги в свет многие теоретико-числовые рекорды, отраженные в ней, будут уже побиты. На самом деле, некоторые из них были превзойдены даже пока мы писали это предисловие. Завершая работу над книгой, мы, можно сказать, жили в том состоянии, которое инженеры-электронщики называют "состояние гонок", поскольку и через Интернет, и устно новые результаты о простых числах сообщались нам даже быстрее, чем мы могли вносить правку в эту книгу. Поэтому в некоторый момент мы приняли решение поставить точку, указав в книге адреса сайтов, на которых можно найти наиболее актуальные на данный момент результаты. Состояние гонок стало естественной частью игры особенно в последние годы, когда в дело включилась мощная вычислительная техника.

Упражнения и проблемы для исследования

В конце каждой главы приведены упражнения, которые обычно следуют в порядке изложения материала данной главы и бывают как очень простыми, так и чрезвычайно сложными. Для того чтобы еще раз продемонстрировать связь между теорией чисел и практикой, мы придали ряду упражнений исследовательский характер и поместили их в качестве проблем для исследования после обычных упражнений (тем не менее, в тексте мы также называем эти проблемы "упражнениями"). Нельзя сказать, что все обычные упражнения легки, однако мы старались относить вопрос к проблемам для исследования в тех случаях, когда его можно было рассматривать как часть длительного и значимого, по нашему мнению, исследования.

Алгоритмы и псевдокод

Мы приложили немало сил (иногда даже на грани нервного срыва), работая над текстом приведенных в книге алгоритмов. Существует точка зрения, согласно которой современное искусство "правильного" псевдокода (т.е. не исполняемого на машине, а предназначенного для чтения человеком) находится в тяжелом кризисе. В большинстве сегодняшних книг, содержащих псевдокод, преобладает несовместимость между его читаемостью и краткостью записи. По-видимому, в настоящее время невозможно достичь обеих этих целей одновременно.

В поисках равновесия в качестве базы для псевдокода нашей книги мы выбрали стиль языка C. В приложении описаны явные примеры того, как перевести на машинный язык различные блоки приведенных в тексте алгоритмов. Мы будем полагать, что наш подход к псевдокоду удался, если произойдут две вещи:

(1) программисты смогут на основе наших алгоритмов с легкостью создавать программы;

(2) все читатели сочтут изложение алгоритмов понятным.

Мы дошли даже до того, что обратились к нескольким талантливым программистам с просьбой перевести алгоритмы нашей книги в настоящие программы, тем самым до какой-то степени проверяя нашу цель (1) (тексты этих программ доступны в разделе Mathematica на сайте http://www.perfsci.com). Тем не менее, как было сказано выше, удовлетворяющий всех симбиоз математики и псевдокода может возникнуть не ранее наступления той эры, когда машины станут более "человекоподобными".

Примечание ко второму изданию

Источников материала и стимулов для подготовки настоящего второго издания было несколько. Во-первых, наши проницательные читатели (которым мы глубоко признательны) обнаружили в первом издании разнообразные ошибки и просили прояснить ряд моментов, а некоторые из читателей даже предлагали включить в книгу новые идеи рассуждений. Во-вторых, постоянно растущие возможности вычислительной теории чисел побуждают нас осветить новые результаты. В-третьих, оба автора преподают, поэтому усовершенствование читаемых ими лекционных курсов способствовало расширению материала первого издания. Помимо исправления ошибок, более доступного изложения и обновленных (на начало 2005 г.) вычислительных достижений, во второе издание включены дополнительные алгоритмы, описанные на введенном нами языке псевдокода. Некоторые из этих алгоритмов можно смело назвать поистине захватывающими открытиями.

ПРИМЕРЫ ДОПОЛНЕНИЙ, СВЯЗАННЫХ С ВЫЧИСЛИТЕЛЬНЫМИ УСПЕХАМИ

• Обновлено значение самого большого известного простого числа (на апрель 2005 г.), а также данные о поиске простых чисел Мерсенна.
• Приведены последние результаты поиска простых близнецов, длинной арифметической прогрессии, состоящей из простых чисел, новые успехи в области распознавания простоты и т.д.
• Описаны недавние достижения в области разложения на множители, большинство из которых (но не все) связаны с субэкспоненциальными методами.
• Приведены недавние рекорды в области дискретного логарифмирования и дискретного логарифмирования на эллиптических кривых (DL и EDL, соответственно).
• Приведены новые границы справедливости гипотезы Римана.

ПРИМЕРЫ ДОПОЛНЕНИЙ, СВЯЗАННЫХ С АЛГОРИТМИЧЕСКИМ ПРОГРЕССОМ

• Добавлен теоретический материал и приведены алгоритмы нового AKS-метода и его усовершенствованных вариантов, которые позволяют установить простоту за полиномиальное время.
• Представлен новый быстрый алгоритм Бернштейна для нахождения чисел, все простые делители которых малы, в большом множестве, даже если это множество не имеет регулярной структуры, что позволяет ускорить методы решета.
• Описан новейший и эффективный алгоритм нахождения наибольшего общего делителя Штеле–Циммермана.
• Даны ссылки на новые результаты в области "промышленных алгоритмов", таких как подсчет числа точек на эллиптической кривой, алгебраические операции на эллиптических кривых, находящие применение в смарт-картах, и "гигаэлементные" быстрые преобразования Фурье (БПФ), т.е. преобразования, способные принимать на входе миллиарды комплексных элементов.
• Неоднородное БПФ, играющее растущую роль в вычислительной теории чисел, включено во второе издание в виде алгоритма alg-drfft.

ПРИМЕРЫ ДОСТИЖЕНИЙ В ТЕОРИИ, ДОБАВЛЕННЫХ ВО ВТОРОЕ ИЗДАНИЕ

• Обсуждается новая сенсационная теорема Грина и Тао о существовании сколь угодно длинной арифметической прогрессии, состоящей исключительно из простых чисел.
• Рассматриваются последние результаты, связанные с гипотезой Ферма–Каталана о том, что существует не более чем конечное множество взаимно простых натуральных чисел x^p, y^q, z^r, для которых x^p + y^q = z^r и 1/p + 1/q + 1/r <= 1. Описан также частный случай, когда одно из этих чисел равно 1: тогда существует единственное решение 8 + 1 = 9, как следует из недавнего чудесного результата Михайлеску, который тем самым решил исходную проблему Каталана.

Разнообразные изменения коснулись списка упражнений. Включены новые упражнения, часто связанные с добавленными алгоритмами. Некоторые упражнения усовершенствованы. Например, в том месте, где в первом издании, по существу, говорилось "Найдите метод для реализации X", во втором издании значится: "Развейте приведенный план алгоритма для реализации X. Расширьте этот метод для решения (более трудной) задачи Y".

Об авторах

Крэндалл Ричард

Выдающийся ученый, специалист в области компьютерных наук. Ранее занимал должности главного криптографа в компании Apple, главного специалиста в компании NeXT, Inc., возглавлял кафедру имени Воллюма в Рид-колледже. Основная область интересов — междисциплинарные научные вычисления. Является автором многочисленных теоретических работ по квантовой физике, биологии, математике и химии, обладателем различных патентов в инженерных областях.

Померанс Карл

Профессор математики в Дартмут-колледже. Защитил диссертацию по математике в Гарвардском университете в 1972 г. Долгое время работал в университете штата Джорджия; заслуженный профессор этого университета. Работал в техническом департаменте компании Bell Labs—Lucent Technologies. Карл Померанс — популярный лектор и обладатель многочисленных премий, в том числе премии Шовене и Конанта за обзорные математические работы. Он широко известен своими исследованиями по вычислительной теории чисел, а также по созданию важнейших алгоритмов, активно используемых в настоящее время.