Введение

LCS35 - это криптографическая задача и головоломка, созданная Роном Ривестом в 1999 году. Задача состоит в том, чтобы вычислить значение, где t - конкретное 14-значное (или 47-битное) целое число, а именно 79685186856218, а n - конкретное 616-значное (или 2048-битное) целое число, которое является произведением двух больших простых чисел (которые не даны). Значение w может быть использовано для расшифровки шифрованного текста z, еще одного целого числа из 616 цифр. Чистый текст предоставляет скрытую информацию о делителе n на факторы, что позволяет легко проверить решение. Идея, лежащая в основе задачи, заключается в том, что единственный известный способ найти значение w, не зная о делителе n, - это t последовательных квадратов. Значение t было выбрано таким образом, что для этого расчета грубой силы потребуется около 35 лет, используя скорости чипов 1999 года в качестве отправной точки, с учетом закона Мура. Ривест отмечает, что "так же, как неудача закона Мура может сделать головоломку сложнее, чем предполагалось, прорыв в искусстве распределения факторов сделает головоломку легче, чем предполагалось". Вызов был установлен на (и берет свое название от) празднования 35-летия Лаборатории компьютерных наук МТИ, теперь входящей в состав Лаборатории компьютерных наук и искусственного интеллекта МТИ. Проблема LCS35 была решена 15 апреля 2019 года, двадцать лет спустя, программистом Бернардом Фабротом. Текст начинается с "!! С днем рождения, ЛКС!" 14 мая 2019 года Рональд Л. Ривест опубликовал новую версию LCS35 (названную CSAIL2019), чтобы продлить головоломку до 2034 года.