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

W 1975 r. Miller pokazał, jak zmniejszyć faktoryzację liczby całkowitej do znalezienia okresu r funkcji f ( x ) = a $N$$r$ 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)=a^x\;\bmod\;N$$f(x+r)=f(x)$$a<N$$r$$r$

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ę $r$$N$$r$$N=pq$$r$$\Omega(\log(N))$$f(x)$$O(\log(N))$$r$klasycznie. 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 ∈ Θ ( $r$$r \in \Theta(N/\log(N))$?$r \in \Theta(\sqrt{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 $r$$O(N/\log(N))$$N$$N$$r \in O(N/\log(N))$$N$ lub r ∈ O ( $r \in O(N))$?$r \in O(\sqrt{N})$

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

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 /$N=pq$$r$$\phi(N)=\mathrm{lcm}(p-1,q-1)$$p-1=2p'$$q-1=2q'$$p',q'$ pierwsza, to jeśli nie będziesz niewiarygodnie szczęśliwy, będziemy mieli $r \geq p'q' \approx N/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 wydarzenia$p$$p=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.$p$$p'$

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