Программист-самоучка решил криптографическую головоломку, которая продержалась 20 лет

Бернар Фабро

В Лаборатории компьютерных наук и искусственного интеллекта при Массачусетском технологическом институте объявили о решении эпохального крипто-паззла. Его специально разработали в 1999-ом, чтобы проверить прогнозы тогдашних передовых светил IT-технологий относительно темпов развития отрасли. Изначально считалось, что на поиск решения задачи уйдет примерно 35 лет, но два независимых претендента справились на 15 лет быстрее.

Головоломка не сильно сложна сама по себе, но она спроектирована по принципу «функции проверяемой задержки» — то есть, ответ можно получить только после определенного количества шагов. Чтобы исключить возможность применения параллельных вычислений, убрать соблазн использования суперкомпьютеров для решения задачи, авторы добавили несколько условий. По сути, нужно как можно быстрее выполнить последовательное возведение в квадрат исходного числа 80 триллионов раз.

Как объясняет Рон Ривест, один из авторов крипто-паззла — идея была в том, чтобы отслеживать, как будут меняться вычислительные мощности для проведения операции возведения в квадрат. И как люди научатся их применять для решения реальных криптографических задач, например, масштабирования блокчейн-структур или организации безопасности использования криптовалют. Он признает, что недооценил темпы развития отрасли, поэтому решение и было найдено много раньше предсказанного срока.

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

Источник