Искусство мыслить рационально. Шорткаты в математике и в жизни

Однако никогда не следует терять надежды, что может найтись хитрая тропа, по которой гору можно обойти. В 2002 году математическое сообщество потрясла новость, что три индийских математика, Маниндра Агравал, Нирадж Каял и Нитин Саксена, работающие в Технологическом институте Канпура, открыли способ тестировать простоту чисел за полиномиальное время, не требующий перехода через гору Римана. Замечательно то обстоятельство, что двое из авторов этого открытия были студентами, писавшими дипломы под руководством Агравала. Даже сам Агравал, старший член этой группы, не был известен большинству математического сообщества. Многим это напомнило об истории великого Рамануджана, который внезапно ворвался на математическую сцену в начале XX века, написав о своих открытиях кембриджскому математику Г. Х. Харди.

Хотя открытие этой группы дало нам тест на простоту чисел, работающий за полиномиальное время и не требующий возможности перехода через гору Римана, в реальной жизни этот алгоритм был не слишком практичным. Как я уже говорил, важно знать степень используемого полинома. Если речь идет о квадратном полиноме, алгоритм работает быстро. Однако исходный алгоритм, который предложили Агравал, Каял и Саксена, имел полиномиальную сложность 12-й степени. Это число уменьшили до 6 американский математик Карл Померанс и голландский математик Хендрик Ленстр, но, как я уже объяснял, хотя с математической точки зрения такое решение и считается шорткатом, на практике оно очень быстро замедляется. По мере роста чисел, которые мы тестируем, работа алгоритма с полиномиальной сложностью шестой степени занимает существенно больше времени.

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

Вспомним, что если некое число не простое и не псевдопростое, то половина чисел, меньших его, не пройдут тест Ферма. Но что, если нам так сильно не повезет, что мы проверим именно те числа, которые пройдут этот тест? Казалось бы, чтобы найти свидетеля составного характера числа, необходимо проверить половину меньших его чисел. Но какова вероятность не попасть на такого свидетеля? Предположим, мы проверили 100 чисел и не нашли ни одного свидетеля. Это означает одно из двух: либо наше число простое или псевдопростое, либо нам действительно не попалось ни одного свидетеля, но вероятность такого события составляет 1 к 2¹⁰⁰. Играть на таких условиях я согласен! – уж слишком мала эта вероятность.

Хотя у нас есть превосходные алгоритмы, как детерминированные, так и вероятностные, позволяющие находить простые числа для создания таких кодов, обычных алгоритмов для взлома этих кодов, по-видимому, не существует. А как насчет чего-нибудь не столь обычного?

Квантовые шорткаты

Одна из проблем, с которыми сталкиваются обычные компьютеры, когда пытаются решить задачу, подобную нахождению простых чисел для деления большого кодового числа, состоит в том, что им приходится проводить одну проверку, прежде чем они могут перейти к следующей. (Уточню для ясности, что в последующих рассуждениях я имею в виду только точное деление, без остатка.) Хорошо бы было разделить компьютер на части так, чтобы все они одновременно проводили разные проверки. Параллельная обработка – очень действенный способ ускорения работы. Взять, к примеру, строительство дома. В состязании на скорость строительства дома, проводившемся в Лос-Анджелесе, победила бригада из 200 строителей, работавших параллельно: они закончили свой дом за четыре часа. Разумеется, некоторые задачи необходимо выполнять последовательно. При строительстве многоэтажного дома или подземного гаража следующий этаж можно добавить, только когда будет построен предыдущий. Но перебор меньших чисел с проверкой того, делится ли на них большее, прекрасно можно производить параллельно. Каждая из таких проверок никак не зависит от результатов всех остальных.

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