Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 8 стр.

Введение                                                                9

      В настоящее время исследования в области построения быстрых
алгоритмов факторизации интенсивно ведутся во всем мире. Ежегодно
проводятся десятки конференций по этой тематике, достигаются новые
рекорды факторизации длинных чисел, исследуются известные проблемы
алгоритмической теории чисел и ставятся новые проблемы. Недавно (в
конце 2009 г.) коллективом европейских ученых, возглавляемым Торштеном
Кляйнъюнгом [30], был установлен новый рекорд по разложению 768-
битового натурального числа с помощью метода решета числового поля.
Предыдущий рекорд в 512-бит был установлен в 2000 г., т.е. переход от 512-
битовых к 768-битовым числам потребовал почти 10 лет. Поэтому следующий
рекорд в 1024 бита при сохранении прежних темпов роста исследований
планируется выполнить не ранее, чем в 2020 г.
      Наша страна практически полностью устранилась от участия в этом
соревновании, что объясняется отсутствием источников финансирования
подобных проектов. Другой причиной является отсутствие литературы на
русском языке по наиболее современным методам факторизации, какими
являются метод квадратичного решета и метод решета числового поля.
Некоторые сведения можно получить из монографий А.В.Черемушкина
«Лекции по арифметическим функциям в криптографии», МЦНМО, 2002,
[79] и О.Н.Василенко «Теоретико-числовые алгоритмы в криптографии»,
МЦНМО, 2003, [64]. Однако, значительный прогресс, достигнутый в этой
области за последние годы, не был отражен в перечисленных изданиях.
      Данная книга, сокращая дефицит в этой области, дает первоначальные
сведения об основных методах факторизации, используемых в современной
теории числовых алгоритмов.
      Автор просит читателей присылать замечания и предложения по
улучшению содержимого книги, а также сведения об возможных опечатках,
встречающихся в тексте, по адресу: [email protected]