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

                                                                          8

этим методом. Сами создатели метода предложили всей математической
общественности для тестового взлома 129-значное десятичное число,
пообещав за его разложение условное вознаграждение в $100. Масла в
огонь подлила также опубликованная в 1977 г. в журнале Sci.Amer. статья
известного математика и популяризатора Мартина Гарднера «A new kind
of cipher that would take millions of years to break»   («Новый алгоритм
шифрования, для взлома которого потребуется миллионы лет») [24].
       Вызов, брошенный всему миру, не остался незамеченным. В
соревнование по поиску быстрых алгоритмов факторизации включилось
огромное количество людей, среди которых были известные математики,
специалисты по теории чисел и криптографы. В результате этой гонки
были    созданы   несколько    алгоритмов    факторизации,     обогативших
алгоритмическую теорию чисел рядом замечательных идей. В конце
80-х г. XX столетия были разработаны самые быстрыми на сегодняшний
день алгоритмы факторизации - метод эллиптических кривых (the El-
liptic Curves method)(X.Ленстра [31]), метод квадратичного решета (the
Quadratic Sieve QS) (C.Pomerance [46]) и метод решета числового поля (the
Number Field Sieve NFS) (J. Pollard [44]). Также Джоном Поллардом были
разработаны более медленные, но намного более простые методы, названные
ρ – метод и (p − 1) – метод Полларда (см. [43]). Фактически, появилось новое
направление в современной алгоритмической теории чисел — исследование
методов проверки простоты целых чисел и методов нахождения делителей
непростых (составных) целых чисел.
       Сама же история с разложением 129-значного числа создателей метода
RSA закончилась в 1994 г., когда с помощью алгоритма квадратичного
решета, реализованного в сети коллективом авторов, возглавляемым
А.Ленстрой, было выполнено разложение этого числа на сомножители. Эта
процедура потребовала колоссальных усилий. Была задействована сеть,
состоящая из 1600 компьютеров, которые проработав 220 дней, подготовили
систему линейных уравнений, содержащую более 0,5 млн неизвестных.
Потом эта система была решена с помощью суперкомпьютера за 2 дня
вычислений.