Max Home IndustryНедавняя и продолжающаяся неразбериха в Интернете — это утверждение и спор о том, что задача факторизации достижима за полиномиальное время. Если бы это было правдой, это поставило бы под угрозу наиболее часто используемую криптографическую систему с открытым ключом и сделало бы нужду в квантовых компьютерах недействительной.
Хорошо, мой последний комментарий слегка насмешливый; Я знаю, что у квантовых компьютеров могут быть и другие приложения, но мечта о взломе кода — это то, что не дает людям спать по ночам.
Это интересная история, потому что она может быть правдой и иллюстрирует все, что не так в мире математики в настоящее время.
Недавно появился нерецензированный препринт с провокационной строкой «Это разрушает криптосистему RSA». Учитывая важность RSA, это то, что привлекает внимание, и, по-видимому, именно поэтому он стоит в начале плотной и трудной для чтения статьи. Обычно такие бумаги в основном игнорируются, но, как и провокационные государственные деятели, они написаны не неизвестным якобы чудаком, а известным, но уже вышедшим на пенсию шифровальщиком Клаусом Питером Шнорром.
В статье описывается развитие идеи, над которой он работал в течение некоторого времени, — особого подхода к факторингу с помощью решеточного алгоритма. Ключевое утверждение в аннотации:
«Мы множим N ≈ 2 400 на n = 47 и N ≈ 2 800 на n = 95. Наше ускоренное сильное прямое-дуальное сокращение [GN08] множителей целых чисел N ≈ 2 400 и N ≈ 2 800 на 4,2 · 109 и 8,4 · 1010 арифметических операций, намного быстрее, чем квадратное сито QS и сито числового поля NFS, и с использованием гораздо меньших простых чисел pn. Это разрушает криптосистему RSA ».
Важно отметить, что удвоение размера целочисленной экспоненты с 400 до 800 только увеличивает количество операций со 109 до 1010 — алгоритм не экспоненциальный, а статья «доказывает» его полиномиальность.
В этот момент вы можете подумать: «Долгое время считалось, что эта проблема связана с NP, но теперь показано, что она находится в P — разве это не доказывает, что P = NP? Если бы это было так, то это было бы более серьезным делом, чем просто уничтожение RSA. Это был бы величайший прорыв в теории информатики за долгое время. К сожалению, это не доказывает, что P = NP, поскольку факторинг никогда не был NP-полным. Если вы можете доказать, что любая NP-полная проблема находится в P, то вы доказали, что все NP-проблемы находятся в P. Долгое время подозревали, что факторинг не является NP-полным, но кто знает.
И кто знает, действительно ли это доказательство является доказательством. Бумага очень плотная, практических примеров нет. Если бы были, то дело было бы решено. Есть несколько хороших больших чисел, которые являются произведением двух простых чисел, которые просто ждут, пока кто-нибудь вычислит их, но этого еще не было сделано. Эти тестовые примеры похожи на испытание каннарейки в клетке на наличие газа — и канарейка все еще очень привязана к своему окуну.
Хорошо, вы можете возразить, что реализация практических результатов — не задача теории ?? и статья действительно претендует на доказательство утверждений. Однако это актуальная проблема математики. Современный стиль математических статей состоит в том, чтобы делать небольшие уступки пониманию или вообще не делать этого. Просто перечислены теоремы и доказательства, и у вас сложится общее впечатление, что никакие усилия не прилагаются к тому, чтобы сделать аргумент понятным. Фактически, создается впечатление, что все, что скрывает, только помогает автору выглядеть лучше и академичнее при написании статьи, которую вы не можете понять. Давно прошли те времена, когда достаточно начитанный математик в одной области мог надеяться прочитать статью в другой и понять. Действительно, даже математики в данной области часто не имеют надежды на понимание. Число математиков, утверждающих, что они что-то доказали, и позволяющих распутывать свои презентации другим, похоже, увеличивается, например, Шиничи Мотидзуки.
Каковы шансы, что статья правильная?
Нехорошо. Он все еще дорабатывается, но сообщение Кигана Райана в Твиттере делает вид, что это простой недостаток. Конечно, может и не быть …
Майк Джеймс — автор «Руководства программиста по теории: объяснение великих идей», книги, которая ставит своей целью представить фундаментальные идеи информатики, включая факторизацию и проблему NP = P, в неформальной и все же информативной форме.