В 1971 году американский математик Дэниел Шэнкс опубликовал метод для задачи, которая не имела ничего общего с цифровыми деньгами. Идея была достаточно проста, чтобы уместиться в одном абзаце, и достаточно хороша, чтобы пережить полвека: вместо того чтобы проходить весь путь с одного конца, пройдите половину пути с каждого конца и встретитесь посередине.
Задача здесь — это задача из предыдущего урока в её благоприятной версии: известен открытый ключ Q, который равен k, умноженному на G, и известно, что k находится между нулём и N. Найти k методом грубой силы стоило бы N шагов. Метод Шэнкса стоит около двух раз квадратного корня из N.
Хитрость заключается в том, чтобы записать k по-другому. Назовите m квадратным корнем из N, округлённым вверх. Любое число между нулём и N можно записать как i, умноженное на m, плюс j, где i и j меньше m — это то же самое разложение, которое вы делаете, говоря, что 47 — это четыре десятка и семь единиц, только с m вместо десяти.
Подставляя в уравнение, Q равно i, умноженному на m, плюс j, всё умноженное на G. Перенесите j на другую сторону: Q минус j, умноженное на G, равно i, умноженному на точку m, умноженную на G. Обратите внимание на то, что произошло. Слева только то, что зависит от j; справа только то, что зависит от i. Обе стороны были разделены.
Отсюда и название. Шаги младенца — это m значений левой стороны: вычисляется Q минус j, умноженное на G, для каждого j, и каждый результат сохраняется в таблице. Шаги гиганта — это m значений правой стороны: вычисляется i, умноженное на точку mG, для каждого i, и каждое из них ищется в таблице. Когда значение совпадает, соответствующие i и j раскрывают k, потому что k равно i, умноженному на m, плюс j.
В битах экономия очевидна. Интервал в семьдесят бит имеет 2^69 кандидатов, и квадратный корень из этого — это около 2^34,5 — чуть более двадцати четырёх миллиардов шагов с каждой стороны. Машина, выполняющая несколько миллиардов операций в секунду, справляется с этим за минуты, а не тысячелетия.
Но приведённый выше расчёт касается времени, и метод требует оплаты в другой валюте. Таблица шагов младенца должна существовать полностью до того, как начнутся шаги гиганта. Это двадцать четыре миллиарда записей, и каждая запись хранит как минимум часть координаты точки и значение j — что-то около тридцати байт на строку, если быть щедрым. Это около семисот пятидесяти гигабайт памяти для интервала в семьдесят бит.
И память растёт с тем же квадратным корнем, что и время. Восемьдесят бит требуют около двадцати четырёх терабайт; девяносто — почти восемьсот. Хранение этого на диске вместо памяти не решает проблему, потому что каждый шаг гиганта делает запрос по непредсказуемому адресу, а диск не любит случайного доступа: метод перестаёт быть ограниченным вычислением и становится ограниченным временем поиска.
Существуют версии, которые уменьшают таблицу, сохраняя только часть каждой точки и соглашаясь проверять ложные срабатывания позже. Они помогают на постоянный коэффициент и не меняют природу проблемы: шаг младенца и шаг гиганта — это метод, который обменивает память на время, и этот обмен имеет физический предел, который наступает быстро.
Именно чтобы избежать этого предела, был найден другой путь — тот, который стоит той же квадратной корни во времени и практически ничего в памяти. Он существует, имеет название животного и является алгоритмом, который разрушил самые большие вызовы, когда-либо решённые. На следующем уроке — кенгуру Полларда.