Программист-самоучка решил криптографическую головоломку на 15 лет раньше срока : Беседка

В 1999 году, когда Лаборатория компьютерных наук Массачусетского технологического института праздновала 35-летие работы, они подарили себе необычный подарок: огромный железный контейнер в форме бумажного пакета — скульптуру, созданную легендарным архитектором Фрэнком Оуэном Гери.

Чтобы открыть эту скульптуру-капсулу с коллекцией инноваций от Била Гейтса, Боба Меткалфа, Тимоти Бернерса-Ли и многих других, нужно решить особенную криптографическую головоломку, разработанную Роном Ривестом, профессором МТИ, специалистом по криптографии.



Сама по себе головоломка не настолько уж сложна, но она спроектирована так, чтобы для ее решения нельзя было использовать параллельные или распределенные вычисления. По сути нужно сделать 80 триллионов последовательных возведений в квадрат изначального числа. То есть если вы начинаете с 3, то на следующем шаге у вас будет 9, затем 81 и так далее. Восемьдесят триллионов раз.

Финальное число вместе с предоставленным задачей дадут короткое предложение с поздравлением. Это предложение и является доказательством решения.

Считалось, что на решение головоломки уйдет около 35 лет, так как по закону Мура именно столько времени пройдет, прежде чем наши компьютеры станут достаточно мощными. Программист-самоучка сумел провести эти вычисления за 3.5 года.



Бернард Фабро из Бельгии провел последние 3.5 года за поиском решения, вооружившись процессором Intel Core i7–6700 и бесплатной программой GNU Multiple Precision Arithmetic Library (GMP).

Как же Фабро удалось так быстро решить задачу? Оборудование и программы стали намного лучше, чем мог себе представить Ривест в 1999 году. Хоть сама задача возведения в степень 80 триллионов раз остается нетронутой, сократилось количество ресурсов, необходимых для возведения в квадрат один раз.

У Фабро программа работала вообще фоном, он лишь регулярно проверял промежуточные результаты, следя за тем, что в вычисления не закралась ошибка. Каждый 1 миллиард возведений (примерно каждые 22 минуты) он сохранял результат.

Компьютер работал 24/7, но Фабро при этом работал, писал программы, компилировал, проверял почту и просто сидел в интернете.

Фабро первым нашел результат, но он не единственный работал над решением головоломки. Команда проекта Cryptophage сейчас ищет решение с помощью специально разработанной программы на ППВМ (программируемой пользователем вентильной матрице). К решению они должны прийти в районе 11 мая, после всего 2 месяцев вычислений.

Вот так решение знаменитой головоломки будет найдено на 15 лет раньше срока двумя независимыми вычислениями — Фабро и Cryptophage. 15 мая состоится официальная церемония вскрытия капсулы.