Доказательства в

В разговоре Разборова опубликовано любопытное небольшое заявление.

Если ФАКТОРИНГ труден, то маленькая теорема Ферма не доказуема в .$S_{2}^{1}$

Что такое и почему текущих доказательств нет в ? S 1 $S_{2}^{1}$$S_{2}^{1}$

является теорией ограниченной арифметики, то есть слабой аксиоматической теорией, полученной строгим ограничением схемы индукцииарифметики Пеано. Это одна из теорий, определенных Сэмом Буссом в егодиссертации, другие общие ссылки включают в себя главу V «МетаматематикиХайека» и «Пудлака» арифметикипервого порядка, «Ограниченную арифметику, логику высказываний и теорию сложности» Крайчека, глава II Бусса «Руководства». теории доказательствилогические основы сложности доказательствКука и Нгуена.$S^1_2$

Вы можете думать о как о теории арифметики, которая имеет индукцию только для предикатов за полиномиальное время. В частности, теория не доказывает, что возведение в степень является полной функцией, теория может доказать, что существуют только объекты полиномиального размера (грубо говоря).$S^1_2$

Во всех известных доказательствах теоремы Ферма Литтла используются либо объекты экспоненциального размера, либо они основаны на точном подсчете размеров ограниченных множеств (что, вероятно, не определяется ограниченной формулой, т. Е. В полиномиальной иерархии, из-за теоремы Тоды).

Результат по FLT, и факторингу проистекает из работы Краичека и Пудлака. Некоторые следствия криптографических гипотез для S 1 2 и EF , и, на мой взгляд, они вводят в заблуждение. Крайчек и Пудлак доказывают, что если факторинг (фактически, IIRC они указывают это для RSA вместо факторинга, но известно, что аналогичный аргумент работает и для факторинга) трудно для рандомизированного полиномиального времени, то S 1 2 не может доказать утверждение, что каждое число взаимно простой с простым числом р имеет конечный показатель степень по модулю р , то есть, существует K такого , что$S^1_2$$S^1_2$$S^1_2$$a$$p$$p$$k$$a^k\equiv1\pmod p$ .

Это правда, что это следствие FLT, но на самом деле это гораздо более слабое утверждение, чем FLT. В частности, это утверждение следует из принципа слабой ямы, который, как известно, доказуем в подсистеме ограниченной арифметики (хотя и более сильной, чем ). Таким образом, аргумент Крайчека и Пудлака показывает, что не доказывает принцип слабой ямы, если факторинг не является простым, и как таковой обеспечивает условное отделение от другого уровня ограниченной арифметической иерархии, скажем, . S 1 2 S 1 2 T 2 $S^1_2$$S^1_2$$S^1_2$$T^2_2$

Напротив, фактический FLT даже не представляется доказуемым в полной ограниченной арифметике , но это не связано с криптографией. Вы можете найти соответствующую дискуссию в моей статье об абелевых группах и квадратичных вычетах в слабой арифметике .$S_2=T_2$