Загадки простых чисел (вторая серия). Проверка на простоту
В 1956 г. знаменитый логик Курт Гедель в письме к Джону фон Нейману спрашивал, можно ли улучшить метод пробного деления, и если можно, то насколько. Фон Нейман не стал заниматься этим вопросом, но позже другие математики ответили Геделю, открыв практические методы нахождения простых чисел длиной до 100 знаков, а иногда даже больше. Эти методы, самый известный из которых называется методом квадратичного решета, появились около 1980 г. Однако почти все они либо вероятностны, либо неэффективны в следующем смысле.
Как увеличивается компьютерное время, необходимое для вычислений, с ростом объема исходных данных?
При тестировании на простоту исходные данные — это не само число, а число знаков в нем. Ключевое различие проводится между двумя группами алгоритмов — алгоритмами, принадлежащими и не принадлежащими к классу Р.
Если время работы алгоритма растет как некая фиксированная степень от размера исходных данных, то алгоритм принадлежит к классу Р; в противном случае — не принадлежит.
Алгоритмы класса Р полезны, тогда как те, что не принадлежат к этому классу, непрактичны. Существует промежуточная полоса своеобразной ничьей земли, где в ход идут другие соображения.
Класс Р получил название от понятия «полиномиальное время» — именно так замысловато математики говорят о постоянных степенях.
Страшный сон любого, кто занимается вычислениями
По стандартам класса Р метод пробного деления работает из рук вон плохо. На школьном уровне, где для проверки предлагаются двух- или трехзначные числа, с ним все в порядке, но при работе со 100-значными числами он абсолютно безнадежен. В общем, пробное деление никак не укладывается в P-класс. Если быть точным, то время выполнения этого алгоритма для любого
n-значного числа приблизительно равняется 10n/2, а эта величина растет быстрее, чем любая фиксированная степень n. С таким типом роста, известным как экспоненциальный, по-настоящему трудно иметь дело, это страшный сон любого, кто занимается вычислениями.
ln(ln n) стремится к бесконечности, но никто никогда не видел, как он это делает.
До 1980-х гг. у всех известных алгоритмов проверки на простоту время вычислений росло экспоненциально. Однако в 1983 г. был найден алгоритм, очень соблазнительно лежащий на ничьей земле вблизи P-территории: тест Адлемана-Померанса-Румели. Его улучшенная версия, разработанная Генри Коэном и Хендриком Ленстрой, имела время вычисления n в степени ln(ln n) (ln x – логарифм по основанию e » 2,71828). Технически ln(ln n) может быть сколь угодно большим, поэтому данный алгоритм не относится к P-классу. Однако это не мешает ему быть пригодным к практическому использованию. Старая шутка гласит: «Доказано, что ln(ln n) стремится к бесконечности, но никто никогда не видел, как он это делает».
Первый тест на простоту, принадлежащий к Р-классу, открыли в
2002 г. Маниндра Агравал и его студенты-дипломники Нирадж Каял и Нитин Саксена. Они придумали алгоритм и доказали, что время его выполнения растет пропорционально не более чем n12; очень скоро эта величина была уменьшена до n7,5. Однако, несмотря на то что их алгоритм относится к P-классу и, соответственно, считается «эффективным», его преимущества не проявляются до тех пор, пока n не становится очень и очень большим. По идее этот алгоритм должен побить тест Адлемана-Померанса-Румели, когда число знаков в n приблизится к 101000. Но такое большое число невозможно разместить не только в память компьютера, но и вообще в известной Вселенной. Зато теперь мы точно знаем, что алгоритмы P-класса для проверки простоты числа существуют. Ясно, что поиск лучших алгоритмов в этой категории — дело стоящее. Ленстра и Померане снизили степень с 7,5 до 6. Если еще некоторые предположения о свойствах простых чисел подтвердятся, степень можно будет снизить до 3, что приблизит нас к практическому применению подобных алгоритмов.
Идея проста настолько, что нужно быть гением, чтобы разглядеть ее
Но самое интересное в алгоритме Агравала-Каяла-Саксены — не результат, а метод. Он прост и отличается новизной. В основе его лежит вариант теоремы Ферма, но, вместо того чтобы работать с числами, команда Агравала использовала многочлены.
Это тот самый случай, когда идея проста настолько, что нужно быть гением, чтобы разглядеть ее. Первый намек на нее проскользнул в статье Агравала и его научного консультанта Сомената Бисваса: авторы предложили вероятностный тест на простоту, основанный на аналоге теоремы Ферма в мире полиномов. Агравал был убежден, что вероятностный компонент этого метода может быть устранен. В 2001 г. его студенты пришли к нему с очень важным техническим замечанием. Начав в нем разбираться, команда углубилась в дебри теории чисел, но постепенно, со временем, все замечания удалось свести к единственному препятствию — вопросу существования простого числа р, такого, чтобы число р –1имело бы достаточно большой простой делитель. Несколько консультаций с коллегами и поиск в Интернете помогли обнаружить теорему, которую Этьен Фуври доказал в 1985 г. при помощи сложных формальных методов. Именно этого команде Агравала недоставало, чтобы доказать работоспособность алгоритма, и последняя деталь головоломки точно встала на место.
Простые числа приобрели огромный вес в криптографии — науке о шифрах
В те времена вся эта история прошла бы незамеченной и никак не повлияла бы на жизнь остального мира. Но в последние 30 лет простые числа приобрели огромный вес в криптографии — науке о шифрах. Шифры важны не только для военных, у коммерческих компаний тоже хватает секретов. Сегодня, в век Интернета, секреты есть у каждого из нас: мы не хотим, чтобы преступники получили доступ к нашим банковским счетам и номерам кредитных карт. Мало того, все чаще в преступных целях используются и другие личные данные, так что хотелось бы уберечь их все, вплоть до клички домашней кошки. Производители компьютеров и интернет провайдеры пытаются снизить этот риск, предлагая пользователям различные системы шифрования. Надо сказать, что внедрение компьютеров изменило как саму криптографию, так и криптоанализ — искусство взлома шифров. В настоящее время разработано множество новых шифров. Один из самых известных шифров, который в 1978 г. придумали Рональд Ривест, Ади Шамир и Леонард Адлеман, основан на использовании простых чисел. Больших простых чисел, примерно 100-значных. Система Ривеста-Шамира-Адлемана (известная как RSA) используется во многих компьютерных операционных системах, встроена в основные протоколы безопасного интернет-соединения, ею широко пользуются правительства, корпорации и университеты. Конечно, не каждое новое открытие, имеющее отношение к простым числам, может повлиять на безопасность вашего банковского счета, но это добавляет теме интереса. Как только удается выяснить что-то новое, что помогает связать простые числа и компьютерные вычисления, это привлекает повышенное внимание. Так случилось и с тестом Агравала-Каяла-Саксены, хотя при всей своей математической элегантности и важности непосредственного практического значения он не имеет, он позволил немного под другим углом рассмотреть общий вопрос криптографии по Ривесту-Шамиру-Адлеману.
(продолжение следует)
Литература
Иэн Стюард «Величайшие математические задачи».
Материалы Википедии.