Dowody w

W przemówieniu Razborowa opublikowano dziwne oświadczenie.

Jeśli FACTORING jest trudny, to małe twierdzenie Fermata nie jest możliwe do udowodnienia w $S_{2}^{1}$ .

Co to jest $S_{2}^{1}$ i dlaczego aktualnych dowodów nie ma w $S_{2}^{1}$ ?

$S^1_2$ jest teorią ograniczonej arytmetyki, to znaczy słabej teorii aksomatycznej uzyskanej przez poważne ograniczenie schematu indukcjiarytmetyki Peano. Jest to jedna z teorii zdefiniowanych przez Sama Bussa wtekście, inne ogólne odniesienia obejmują rozdział V Hájeka i Metamatematykęarytmetyki pierwszego rzęduPudláka, „Arytmetykę ograniczoną, logikę zdań i teorię złożoności” Krajíčka, rozdział Bussa IIpodręcznika teorii dowoduorazlogiczne podstawyCooka i Nguyena dotyczącezłożoności dowodu.

Możesz myśleć o jako teorii arytmetyki, która indukuje się tylko dla predykatów czasu wielomianowego. W szczególności teoria nie dowodzi, że potęgowanie jest funkcją całkowitą, teoria może udowodnić, że istnieją tylko obiekty wielomianowe (mówiąc luźno).$S^1_2$

Wszystkie znane dowody małego twierdzenia Fermata wykorzystują obiekty o wielkości wykładniczej lub polegają na dokładnym zliczaniu rozmiarów zbiorów ograniczonych (co prawdopodobnie nie jest możliwe do zdefiniowania przez ograniczoną formułę, tj. W hierarchii wielomianowej z powodu twierdzenia Tody).

Wynik dotyczący FLT, i faktoringu wynika z pracy Krajíčka i Pudláka. Niektóre konsekwencje kryptograficznych przypuszczeń dla S 1 2 i EF , i moim zdaniem jest to dość mylące. Krajíček i Pudlák udowadniają, że jeśli faktoring (faktycznie IIRC podaje to dla RSA zamiast faktoringu, ale wiadomo, że podobny argument działa również dla faktoringu) jest trudny dla losowego wielomianu, wówczas S 1 2 nie może udowodnić, że każda liczba względnie pierwsze do liczby pierwszej p ma skończoną wykładnik modulo p , to znaczy istnieje k takie, że$S^1_2$$S^1_2$$S^1_2$$a$$p$$p$$k$$a^k\equiv1\pmod p$ .

To prawda, że ​​jest to konsekwencja FLT, ale w rzeczywistości jest to znacznie słabsze stwierdzenie niż FLT. W szczególności stwierdzenie to wynika z zasady słabej szuflady, o której wiadomo, że jest sprawdzalna w podsystemie ograniczonej arytmetyki (choć silniejszej niż ). Zatem argument Krajíčka i Pudláka pokazuje, że nie dowodzi zasady słabej szuflady, chyba że faktoring jest łatwy, i jako taki zapewnia warunkowe oddzielenie od innego poziomu ograniczonej hierarchii arytmetycznej, powiedzmy . S 1 2 S 1 2 T 2 $S^1_2$$S^1_2$$S^1_2$$T^2_2$

W przeciwieństwie do tego, rzeczywisty FLT nie wydaje się nawet możliwy do udowodnienia w pełnej arytmetyki , ale nie jest to związane z kryptografią. Odpowiednią dyskusję można znaleźć w mojej pracy Grupy abelowe i pozostałości kwadratowe w słabej arytmetyki .$S_2=T_2$