(Kryptograficzne) problemy do rozwiązania w wielomianowej liczbie kroków arytmetycznych

W artykule Adi Shamira [1] z 1979 r. Pokazuje, że faktoring można wykonać w wielomianowej liczbie kroków arytmetycznych . Fakt ten został powtórzony i dlatego zwrócił moją uwagę w niedawnej pracy Borweina i Hobarta [2] w kontekście programów liniowych (SLP).

Ponieważ byłem raczej zaskoczony, gdy to przeczytałem, mam następujące pytanie: Czy są jakieś inne problemy kryptograficzne, a może także inne istotne problemy, które można rozwiązać w wielomianowej liczbie kroków za pomocą SLP i które obecnie nie są znane z możliwości rozwiązania wydajnie na „normalnym” klasycznym komputerze?

[1] Adi Shamir, Faktoring Numbers in$O(\log n)$kroki arytmetyczne . Information Processing Letters 8 (1979) S. 28–31

[2] Peter Borwein, Joe Hobart, Niezwykła moc podziału w programach prostych , The American Mathematical Monthly Vol. 119, nr 7 (sierpień ‒ wrzesień 2012 r.), S. 584–592

Nie przeczytałem też artykułu, ale streszczenie wydaje się mówić, że wymagana jest wykładnicza liczba operacji bitowych.

Praca Czebyszewa na temat zgodności i jego przeformułowania w algorytmie AKS pokazuje, że generowanie liczb pierwszych odbywa się w P. Dlatego podział próby daje czynniki niebanalne. W takim przypadku dla pewnej liczby N można oczekiwać gęstości liczb pierwszych 1 / ln (N).

Co więcej, możesz spojrzeć na rozprawę doktorską Turinga z 1937 r. Na ten temat.