Dolne granice okresu w rozkładzie na liczby całkowite?

11

W 1975 r. Miller pokazał, jak zmniejszyć faktoryzację liczby całkowitej do znalezienia okresu r funkcji f ( x ) = a xNr 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 się, że trudno jest znaleźć klasyczny komputer na r .f(x)=axmodNf(x+r)=f(x)a<Nrr

Moje pytanie brzmi teraz: czy są jakieś znane dolne granice dla losowego N ? Czy istnieją granice na R podano N- = P Q jest wybrany z RSA? Oczywiście r musi być Ω ( log ( N ) ), ponieważ w przeciwnym razie można po prostu ocenić f ( x ) na O ( log ( N ) ) kolejnych punktach, aby dowiedzieć się rrNrN=pqrΩ(log(N))f(x)O(log(N))rklasycznie. Czy wystarczyłoby złamać RSA, gdyby istniał klasyczny algorytm faktoringu, który działa tylko przy pewnych założeniach dotyczących rozkładu , np. R Θ ( N / log ( N ) ) lub r Θ ( rrΘ(N/log(N))?rΘ(N)

Prezentacja Carla Pomerance'a na temat „Modu multiplikatywnego rzędu nśrednio przytacza dowody, że oznacza średnio O ( N / log ( N ) ) dla całego N , ale nie jestem pewien, czy klasyczny algorytm, który może uwzględniać N pod hipoteza r O ( N / log ( N ) ) ostatecznie złamałaby RSA. Czy N można niekorzystnie wybrać, aby mieć r O ( N )rO(N/log(N))NNrO(N/log(N))N lub r O ( rO(N))?rO(N)

(Uwaga: Istnieje pokrewne pytanie dotyczące faktoringu ogólnego vs. faktoringu RSA)

Martin Schwarz
źródło

Odpowiedzi:

17

Jeśli , okres r będzie zawsze dzielnikiem ϕ ( N ) = l c m ( p - 1 , q - 1 ) . Jeśli wybierzesz p - 1 = 2 p i q - 1 = 2 q dla p , q q N / 4N=pqrϕ(N)=lcm(p1,q1)p1=2pq1=2qp,q pierwsza, to jeśli nie będziesz niewiarygodnie szczęśliwy, będziemy mieli rpqN/4. Wierzę również, że możemy skutecznie znaleźć liczb pierwszych z p = 2 p ' + 1 przy wyborze kandydatów losowo i ich testowanie (to prawda, że jeśli wydarzeniapp=2p+1 i p ' są prime są mniej więcej niezależne; nie wiem, czy to zostało udowodnione). Tak więc, starannie wybierając liczby pierwsze, RSA będzie nadal zabezpieczone przed atakami, nawet przy dodatkowej hipotezie o łatwym faktorowaniu.pp

Podejrzewam, że losowe liczby lub losowe N = p q bardzo rzadko mają r O ( NN=pq, ale nie mam na to dowodu. HipotezarO(rO(N)jest wyjątkowo silny i nie zdziwiłbym się, gdyby w tym przypadku znany był już wydajny algorytm faktoringu.rO(N)

Peter Shor
źródło