Dalam sebuah pembicaraan oleh Razborov, sebuah pernyataan kecil yang aneh diposting.
Jika FACTORING sulit, maka teorema kecil Fermat tidak dapat dibuktikan dalam .
Apa itu dan mengapa bukti saat ini tidak ada di ? S 1 2
Dalam sebuah pembicaraan oleh Razborov, sebuah pernyataan kecil yang aneh diposting.
Jika FACTORING sulit, maka teorema kecil Fermat tidak dapat dibuktikan dalam .
Apa itu dan mengapa bukti saat ini tidak ada di ? S 1 2
adalah teori aritmatika terbatas, yaitu teori aksiomatik lemah yang diperoleh dengan sangat membatasi skema induksi aritmatika Peano . Ini adalah salah satu teori yang didefinisikan oleh Sam Buss dalam tesisnya , referensi umum lainnya termasuk Bab V dari Hájek dan Pudam Metamathematics dari aritmatika orde pertama , “Aritmatika Terikat, logika proposisional, dan teori kompleksitas” karya Buss, Bab II dari Buku Pegangan teori bukti , dan Cook and Nguyen Foundation logis dari kompleksitas bukti .
Anda dapat menganggap sebagai teori aritmatika yang hanya memiliki induksi untuk predikat waktu polinomial. Secara khusus, teori tidak membuktikan bahwa eksponensial adalah fungsi total, teori dapat membuktikan hanya ada objek dengan ukuran polinomial (secara longgar).
Semua bukti yang diketahui dari Teorema Kecil Fermat menggunakan objek ukuran eksponensial, atau mereka bergantung pada penghitungan yang tepat dari ukuran set terikat (yang mungkin tidak dapat ditentukan oleh rumus terikat, yaitu, dalam hierarki polinomial, karena teorema Toda).
Hasil pada FLT, , dan anjak piutang berasal dari kertas Krajíček dan Pudlák. Beberapa konsekuensi dugaan kriptografis untuk dan EF , dan menurut saya itu cukup menyesatkan. Apa yang dibuktikan oleh Krajíček dan Pudlák adalah bahwa jika anjak piutang (sebenarnya, IIRC mereka menyatakannya untuk RSA dan bukan anjak piutang, tetapi diketahui bahwa argumen serupa juga berfungsi untuk anjak piutang) sulit untuk waktu polinomial acak, maka tidak dapat membuktikan pernyataan bahwa setiap angka coprime ke bilangan prima memiliki modul eksponen yang terbatas , yaitu, terdapat sedemikian sehingga . S 1 2 S 1 2 a p p k a k ≡ 1
Memang benar ini adalah konsekuensi dari FLT, tetapi sebenarnya itu adalah pernyataan yang jauh lebih lemah dari FLT. Secara khusus, pernyataan ini mengikuti prinsip pigeonhole yang lemah, yang diketahui dapat dibuktikan dalam subsistem aritmatika terbatas (meskipun lebih kuat dari ). Dengan demikian, argumen Krajíček dan Pudlák menunjukkan bahwa tidak membuktikan prinsip pigeonhole yang lemah kecuali jika anjak mudah, dan dengan demikian memberikan pemisahan bersyarat dari tingkat hierarki aritmetika terikat lainnya, katakan . S 1 2 S 1 2 T 2 2
Sebaliknya, FLT yang sebenarnya bahkan tidak dapat dibuktikan dalam aritmatika terikat penuh , tetapi ini tidak terkait dengan kriptografi. Anda dapat menemukan beberapa diskusi yang relevan dalam makalah saya kelompok Abelian dan residu kuadratik dalam aritmatika lemah .