В 1950-х годах советский математик Анатолий Карацуба обнаружил способ уменьшить сложность алгоритма умножения. В его алгоритме число шагов увеличивается не быстрее, чем N1,58 — это существенно меньше, чем N2. Впрочем, если читателю вздумается ознакомиться с алгоритмом Карацубы, он обнаружит, что при этом сам метод существенно сложнее обычного школьного умножения. Согласно оценкам, его преимущество проявляется, начиная с чисел, имеющих не менее 10 000 десятичных разрядов.
Десять лет спустя проблемой занялись два немецких математика, которые предложили еще более экономичный алгоритм — с числом шагов не больше чем N * logN * log(logN). Алгоритм Шёнхаге — Штрассена, однако, тоже не оптимален, эти же математики предположили, что возможно перемножать большие числа так, чтобы число шагов не росло быстрее чем N * logN. Однако ни предложить конкретный способ, ни даже доказать его возможность не удавалось вплоть до настоящего времени.
Именно эту задачу и решили Харви и Ван дер Хэвен. Они предложили способ построить именно такой алгоритм.
Насколько подобные математические приемы способны ускорить реальные вычисления? По словам Харви, чтобы перемножить два числа с миллиардом десятичных знаков, современному компьютеру понадобится около месяца. Применение алгоритма Шёнхаге — Штрассена позволит уложиться в 30 секунд. Алгоритм, способ построения которого предлагает сам Харви, справится с задачей еще быстрее. Более того, математики предполагают, что это, вероятно, и есть теоретически возможный предел скорости умножения, хотя строго доказать эту гипотезу им пока не удалось. Однако если это так, данную математическую задачу можно считать окончательно решенной.
Насколько большим должно быть число, чтобы алгоритм Харви — Ван дер Хэвена дал преимущество в скорости вычисления? «Понятия не имею», — честно отвечает Харви, однако в своей статье он приводит в качестве примера умножение, дающее результат 10214857091104455251940635045059417341952. Это действительно очень большое число: во всей видимой Вселенной, к примеру, содержится всего порядка 1080 элементарных частиц.
Однако тот факт, что столь большие числа не соответствуют количеству чего бы то ни было в реальном мире, вовсе не значит, что открытие математиков бесполезно. Умножение — неотъемлемая часть других вычислительных процедур, таких как деление или извлечение корней. Данный результат окажется полезным и тем, кто намерен вычислить много-премного знаков числа пи или, к примеру, расширить список известных человечеству простых чисел.
У этой работы есть еще одно интересное следствие. При обосновании преимуществ квантового компьютера нередко приводят в качестве примера алгоритмы шифрования. Эти алгоритмы часто построены на разложении очень больших чисел на множители. Квантовый алгоритм Шора справляется с этой задачей довольно легко, тогда как для классического алгоритма разложение достаточно большого числа потребует времени, сравнимого с возрастом Вселенной. Однако в этих примерах всегда неявно подразумевается, что эффективность классического алгоритма — величина, определенная раз и навсегда. Работа австралийского и французского математиков показывают, что это далеко не так. А вдруг математики будущего предложат настолько изящный классический способ разложения числа на множители, что существующие шифры легко можно будет взломать не только на квантовом, но и на классическом компьютере? Сравнение квантовых и классических алгоритмов некорректно, пока не показано, что и тот и другой действительно являются лучшими из теоретически возможных.
Остается добавить, что работа математиков пока опубликована онлайн, и их коллегам еще предстоит тщательно проверить все выкладки. Авторы выражают надежду, что они ничего не перепутали. Тем временем каждый из читателей имеет возможность самостоятельно проверить все вычисления и, возможно, найти в них ошибку.