Алгоритм, который решил самые большие из известных задач, получил название животного, потому что сам автор объяснил его так. В 1978 году британский математик Джон Поллард описал метод, в котором два кенгуру прыгают по полю: один ручной, чье положение известно, и другой дикий, которого нужно найти. Ручной оставляет ловушки там, где прыгает. Рано или поздно дикий наступает на одну из них.
Перевод на кривую прямой. Ручной кенгуру начинает с известной точки внутри интервала — скажем, с середины — и расстояние, которое он уже прошел, фиксируется при каждом прыжке. Дикий кенгуру начинает с точки Q, публичного ключа цели, расстояние от которой до начала и есть искомое число.
Деталь, которая делает все это возможным, заключается в размере прыжков. Он не выбирается случайно: он вычисляется из координаты точки, где находится кенгуру. Два кенгуру, которые наступают на одну и ту же точку, делают одинаковый следующий прыжок, и следующий, и следующий — с момента первой встречи оба пути идентичны навсегда. Это и превращает случайную встречу в обнаруживаемое столкновение.
Когда происходит столкновение, расчет тривиален. Известно, сколько прошел ручной, известно, сколько прошел дикий от Q, и известно, что оба находятся в одном и том же месте. Разница между двумя расстояниями, сложенная с начальной точкой ручного, и есть приватный ключ.
Остается решить практическую проблему: как заметить, что столкновение произошло, не сохраняя все точки, через которые прошел каждый кенгуру? Ответ — отличимые точки. Выбирается редкое и легко проверяемое свойство — например, чтобы координата x заканчивалась двадцатью нулевыми битами — и точка фиксируется только тогда, когда она обладает этим свойством. Примерно один из миллиона прыжков. Поскольку после столкновения оба пути совпадают, они оба в конечном итоге наступят на одну и ту же отличимую точку, и именно там фиксируется встреча.
Итоговый расчет — это тот же квадратный корень из предыдущего метода — что-то около двух раз корня из ширины интервала — с решающим отличием: используемая память — это таблица отличимых точек, которая помещается в несколько мегабайт. Там, где метод "шаг младенца и шаг гиганта" требовал семьсот пятьдесят гигабайт для семидесяти бит, кенгуру требует почти ничего.
Добавьте к этому, что он почти идеально параллелизуется. Выпустите тысячу ручных и тысячу диких кенгуру, каждый на отдельной машине, все записывающие отличимые точки на общий сервер: общий объем работы не изменится, а календарное время сократится в тысячу раз. Техника параллелизации с отличимыми точками была разработана в 1999 году Полом ван Уршотом и Майклом Винером, и именно она делает метод практичным в масштабе.
Есть два условия, и оба важны.
Первое — публичный ключ должен быть известен. Кенгуру прыгает по точкам кривой; если у вас есть только адрес, нет начальной точки для дикого, и метод не применим. Это был Урок 1, который разделил два мира, и здесь это разделение имеет значение.
Второе — интервал должен быть известен. Ручной кенгуру должен начать недалеко от дикого, чтобы встреча произошла за несколько прыжков; на поле размером с всю кривую ожидание снова становится 2^128. Без знания участка нет места для ожидания.
Обратите внимание, что это значит для обычного кошелька. Ваш публичный ключ становится доступным, как только вы тратите в первый раз, и все же интервала нет: он был выбран случайно из всех 256 бит, и кенгуру понадобилось бы 2^128 прыжков. Оба условия должны выполняться вместе, и в задаче они выполняются по конструкции — потому что тот, кто ее составил, специально выбрал интервал.
Остается рассмотреть оборудование, которое выполняет эти прыжки, и где оно останавливается. В следующем уроке — видеокарты, ASIC и реальное расстояние между 2^40 и 2^70.