Pruebas en

En una charla de Razborov, se publica una pequeña y curiosa declaración.

Si FACTORING es difícil, entonces el pequeño teorema de Fermat no es demostrable en $S_{2}^{1}$ .

¿Qué es $S_{2}^{1}$ y por qué las pruebas actuales no están en $S_{2}^{1}$ ?

$S^1_2$ es una teoría de la aritmética limitada, es decir, una teoría axiomática débil obtenida restringiendo severamente el esquema de inducción dela aritméticadePeano. Es una de las teorías definidas por Sam Buss en sutesis, otras referencias generales incluyen el Capítulo V de Hájek y la Metamatemática de Pudlák dearitmética de primer orden, "Aritmética limitada, lógica proposicional y teoría de la complejidad de Krajíček", Capítulo II delManual deBussde la teoría de la prueba, y losfundamentos lógicos deCook y Nguyen de lacomplejidad de la prueba.

Puede pensar en como una teoría de la aritmética que tiene inducción solo para predicados de tiempo polinomial. En particular, la teoría no prueba que la exponenciación sea una función total, la teoría puede probar que existen solo objetos de tamaño polinómico (hablando en términos generales).$S^1_2$

Todas las pruebas conocidas del pequeño teorema de Fermat utilizan objetos de tamaño exponencial, o se basan en el recuento exacto de tamaños de conjuntos acotados (que probablemente no sea definible por una fórmula acotada, es decir, en la jerarquía polinómica, debido al teorema de Toda).

El resultado en FLT, y factorización proviene del artículo de Krajíček y Pudlák Algunas consecuencias de conjeturas criptográficas para S 1 2$S^1_2$$S^1_2$ y EF , y en mi opinión es bastante engañoso. Lo que Krajíček y Pudlák prueban es que si factorizar (en realidad, IIRC lo declaran para RSA en lugar de factorizar, pero se sabe que un argumento similar funciona para factorizar también) es difícil para el tiempo polinómico aleatorio, entonces no puede probar la afirmación de que cada número una primos entre sí a un número primo p tiene finita exponente módulo p , es decir, no existe k tal que$S^1_2$$a$$p$$p$$k$ .$a^k\equiv1\pmod p$

Es cierto que esto es una consecuencia de FLT, pero de hecho es una declaración mucho más débil que FLT. En particular, esta declaración se desprende del principio del casillero débil, que se sabe que es demostrable en un subsistema de aritmética limitada (aunque es más fuerte que ). Así, el argumento de Krajíček y Pudlák muestra que S 1 $S^1_2$$S^1_2$ no prueba el principio débil del casillero a menos que la factorización sea fácil, y como tal proporciona una separación condicional de de otro nivel de la jerarquía aritmética limitada, digamos T 2 2 .$S^1_2$$T^2_2$

Por el contrario, el FLT real ni siquiera parece ser demostrable en aritmética totalmente limitada , pero esto no está relacionado con la criptografía. Puede encontrar alguna discusión relevante en mi artículo Grupos abelianos y residuos cuadráticos en aritmética débil .$S_2=T_2$