Умножение — основа работы компьютеров: шифрование, роботы, искусственный интеллект, обработка аудио — всё это опирается на перемножение чисел, иногда огромных. Школьный алгоритм, когда числа записывают столбиком и перемножают каждую цифру, работает за O(n²) шагов — удвоение длины чисел замедляет вычисления в четыре раза. Веками математики считали это пределом. В 1960 году на семинаре в МГУ профессор Андрей Колмогоров выдвинул гипотезу, что быстрее O(n²) умножать нельзя. Через неделю 23-летний студент Анатолий Карацуба принёс опровержение. Колмогоров сам написал доказательство и опубликовал его в трудах Академии наук, указав Карацубу первым автором — тот узнал о статье, когда получил оттиски по почте.
Карацуба понял: дорогие умножения можно заменять на дешёвые сложения. Сложение n‑значных чисел занимает O(n) — проход по цифрам один раз, а не для каждой цифры второго числа. Для 12 × 34 он разбил числа на десятки и единицы: a=1, b=2, c=3, d=4. В обычном раскрытии (10a+b)×(10c+d) нужны четыре умножения: ac, ad, bc, bd. Карацуба заметил: если посчитать ac и bd, то средний член (ad+bc) получается через одно умножение — (a+b)×(c+d) − ac − bd. Итого три умножения вместо четырёх. При рекурсивном применении к большим числам экономия накапливается — алгоритм работает за O(n^1.585). Для тысячезначных чисел школьный метод требует миллиона операций, Карацуба — меньше 57 тысяч.
Этот алгоритм встроен в Python. Когда числа достигают примерно 630 десятичных знаков, Python переключается с обычного умножения на метод Карацубы (порог — 70 цифр в системе с основанием 2³⁰). Открытие положило начало гонке за предельной скоростью умножения. Кульминация наступила в 2019 году: математики Дэвид Харви и Йорис ван дер Хувен описали алгоритм, работающий за O(n × log n). Это почти так же быстро, как сложение или даже простое чтение чисел. Но есть нюанс: метод оказывается эффективнее существующих только на числах настолько больших, что никогда не пригодится на практике — классический пример «галактического алгоритма». Тем не менее он установил рекорд. Сегодня многие подозревают, что O(n × log n) — истинный предел умножения, но формального доказательства нет. История уже однажды опровергала общее мнение, и этот вопрос остаётся святым Граалем для узкой области математики.