En 1975, Miller mostró cómo reducir la factorización del número entero para encontrar el período r de una función f ( x ) = a x tal que f ( x + r ) = f ( x ) con algunos elegidos al azar a < N . Es bien sabido que el algoritmo de Shor puede encontrar r eficientemente en una computadora cuántica, mientras que se cree que es intratable que una computadora clásica encuentre r .
Mi pregunta ahora es: ¿Hay algún límite inferior conocido en para N aleatorio ? ¿Hay algún límite en r dado que N = p q se elige como en RSA? Claramente, r debe ser Ω ( log ( N ) ) ya que de lo contrario uno podría evaluar f ( x ) en O ( log ( N ) ) puntos sucesivos para descubrir rClásicamente. ¿Sería suficiente romper RSA si hubiera un algoritmo de factorización clásico que solo funciona bajo alguna suposición sobre la distribución de , por ejemplo, r ∈ Θ ( N / log ( N ) ) o r ∈ Θ ( √?
Una presentación de Carl Pomerance en " El orden multiplicativo mod en promedio " cita evidencia de que es O ( N / log ( N ) ) en promedio sobre todo N , sin embargo, no estoy seguro de si un algoritmo clásico que puede factorizar N bajo la hipótesis de r ∈ O ( N / log ( N ) ) rompería de manera concluyente RSA. ¿Puede N elegirse de manera adversa para tener r ∈ O ( N ) o r ∈ O ( √?
(Nota: hay una pregunta relacionada sobre factorización genérica versus factorización RSA)
fuente