W 1975 r. Miller pokazał, jak zmniejszyć faktoryzację liczby całkowitej do znalezienia okresu r funkcji f ( x ) = a x 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 .
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ę 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 ∈ Θ ( √?
Prezentacja Carla Pomerance'a na temat „Modu multiplikatywnego rzędu ” ś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 ) lub r ∈ O ( √?
(Uwaga: Istnieje pokrewne pytanie dotyczące faktoringu ogólnego vs. faktoringu RSA)
źródło