В этой бочке меда есть, однако, своя ложка дегтя. Бывают числа, которые ведут себя как простые, и никакие свидетели Ферма их не выдают, но простыми они не являются. Их называют псевдопростыми. Тем не менее в конце 1980-х годов два математика, Гари Миллер и Майкл Рабин, сумели усовершенствовать метод Ферма и разработать безошибочный тест на простоту чисел, работающий за полиномиальное время. Единственная оговорка состояла в том, что для этого им пришлось предположить, что существует возможность покорения одной чрезвычайно высокой вершины – гипотезы Римана (или ее обобщенного варианта).

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

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

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