Jest to „pytanie historyczne” bardziej niż pytanie badawcze, ale czy klasyczne sprowadzenie do ustalania porządku w algorytmie Shora dla faktoryzacji zostało początkowo odkryte przez Petera Shora, czy też było wcześniej znane? Czy istnieje artykuł opisujący redukcję, która poprzedza Shora, czy jest...
Książka Arory i Baraka przedstawia faktoring jako następujący problem: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Dodają, w dalszej części...
To jest cross-post z math.stackexchange. Niech FACT oznaczają problemu faktoringowej całkowitą: podany znaleźć liczb pierwszych p i ∈ N , a całkowite e I ∈ N , tak, że N = Π k i = 0 p e ı ı .n∈N,n∈N,n \in \mathbb{N},pi∈N,pi∈N,p_i \in \mathbb{N},ei∈N,ei∈N,e_i \in...
Niech PRIMES (inaczej testowanie pierwotności ) będzie problemem: Biorąc pod uwagę liczbę naturalną , czy n jest liczbą pierwszą?nnnnnn Niech FACTORING będzie problemem: Biorąc pod uwagę liczby naturalne , m przy 1 ≤ m ≤ n , czy n ma współczynnik d przy 1 < d < m ?nnnmmm1≤m≤n1≤m≤n1...
Faktoring nie jest znany jako NP-zupełny. To pytanie dotyczyło konsekwencji faktoringu jako NP-zupełnego. Co ciekawe, nikt nie pytał o konsekwencje faktoringu w P (być może dlatego, że takie pytanie jest banalne). Więc moje pytania to: Jakie byłyby teoretyczne konsekwencje faktoringu w P? Jak...
Biorąc pod uwagę liczbę całkowitą długości n bitów, jak trudne jest wyprowadzenie liczby czynników pierwszych (lub alternatywnie liczby czynników) N ?N.NNnnnN.NN Gdybyśmy znali podstawową faktoryzację , byłoby to łatwe. Gdybyśmy jednak znali liczbę czynników pierwszych lub liczbę czynników...
Wpis na blogu Scotta Aaronsona przedstawił dziś listę interesujących otwartych problemów / zadań w złożoności. Jeden zwrócił moją uwagę: Zbuduj bibliotekę publiczną instancji 3SAT z jak najmniejszą liczbą zmiennych i klauzul, które mogłyby mieć godne uwagi konsekwencje, jeśli zostaną rozwiązane....
Czy są jakieś referencje na ten
To pytanie zostało przeniesione z Computer Science Stack Exchange, ponieważ można na nie odpowiedzieć na Theoretical Computer Science Stack Exchange. Migrował 3 lata temu . W artykule naukowym z 2016 r. „ Realizacja skalowalnego algorytmu Shora ” [ 1 ] autorzy
Szukam odwołania do następującego wyniku: Dodanie dwóch liczb całkowitych do reprezentacji faktoryzowanej jest tak trudne, jak dodanie dwóch liczb całkowitych do zwykłej reprezentacji binarnej. (Jestem prawie pewien, że tam jest, ponieważ zastanawiałem się nad tym, a potem byłem...
Powszechnie wiadomo, że potęgowanie modułowe (główna część operacji RSA) jest drogie obliczeniowo i, o ile rozumiem, preferowaną metodą jest potęgowanie modułowe Montgomery'ego . Modułowe potęgowanie jest również wyraźnie widoczne w algorytmie faktoringu kwantowego i tam również jest drogie. Więc:...
W swoim artykule z 1995 r. „ Algorytmy czasowe wielomianowe dla faktoryzacji pierwotnej i logarytmów dyskretnych na komputerze kwantowym” Peter W. Shor omawia ulepszenie części algorytmu faktoryzacji polegającej na ustalaniu kolejności. Standardowe wyjścia algorytm , dzielnik w kolejności R o x...
Właśnie przeczytałem pytanie „ Czy rozkład liczb całkowitych jest problemem NP-zupełnym? ” ... więc postanowiłem poświęcić trochę mojej reputacji :-) zadając kolejne pytanie mając :QQQP(Q is trivial)≈1P(Q is trivial)≈1P(\text{Q is trivial}) \approx 1 Jeśli jest wyrocznią, która rozwiązuje...
Czytając blog Dicka Liptona, natknąłem się na następujący fakt pod koniec jego posta Bourne Factor : Jeśli dla każdego istnieje relacja formy ( 2 n ) ! = M - 1 Σ k = 0 k b c k k , gdzie m = p O l r ( n ) , a każdy z k , b k i c k są s O l y ( n ) na długości bitowej, a następnie faktoring ma...
W „ Poradzie dla początkującego studenta ” Manuela Bluma : LEONID LEVIN wierzy, jak to robię, niezależnie od odpowiedzi na P = NP? problem, to nie będzie tak, jak myślisz, że powinno być. Podał też wspaniałe przykłady. Po pierwsze, podał FACTORING ALGORITHM, który jest optymalnie optymalny, aż...
Biorąc kompozytu Pole numeru sita ogólnie najlepiej znane algorytm faktoryzacji całkowitymi faktoryzacji N . Jest to algorytm randomizowany i otrzymujemy oczekiwaną złożoność O ( e √N∈NN∈NN\in\Bbb NNNNdo
W 1975 r. Miller pokazał, jak zmniejszyć faktoryzację liczby całkowitej do znalezienia okresu r funkcji f ( x ) = a xN.NNrrr taki, że f ( x + r ) = f ( x ) z niektórymi losowo wybranymi a < N . Dobrze wiadomo, że algorytm Shora możeefektywnieznajdować r na komputerze kwantowym, podczas gdy uważa...