Программист-самоучка решил криптографическую головоломку, которая продержалась 20 лет
Головоломка не сильно сложна сама по себе, но она спроектирована по принципу «функции проверяемой задержки» — то есть, ответ можно получить только после определенного количества шагов. Чтобы исключить возможность применения параллельных вычислений, убрать соблазн использования суперкомпьютеров для решения задачи, авторы добавили несколько условий. По сути, нужно как можно быстрее выполнить последовательное возведение в квадрат исходного числа 80 триллионов раз.
Как объясняет Рон Ривест, один из авторов крипто-паззла — идея была в том, чтобы отслеживать, как будут меняться вычислительные мощности для проведения операции возведения в квадрат. И как люди научатся их применять для решения реальных криптографических задач, например, масштабирования блокчейн-структур или организации безопасности использования криптовалют. Он признает, что недооценил темпы развития отрасли, поэтому решение и было найдено много раньше предсказанного срока.
Победителем стал программист-самоучка Бернар Фабро из Бельгии, который на обычном домашнем ПК с процессором Intel Core i7-6700 и библиотекой GNU Multiple Precision Arithmetic Library за 3,5 года провел все необходимые вычисления. Конкуренцию ему составила команда профессора Саймона Пефферса, которая воспользовалась новым алгоритмом возведения в квадрат от ученого Эрдинца Озтюрка из Университета Сабанчи. Они применили программируемый аппаратный ускоритель FPGA, и вычисление результата с его помощью займет всего два месяца. Но ответ будет получен только 11 мая 2019-го, поэтому победа присуждена Фабро.