¿Límites inferiores en el período de factorización entera?

11

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 xNr 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 .f(x)=axmodNf(x+r)=f(x)a<Nrr

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 rrNrN=pqrΩ(log(N))f(x)O(log(N))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 Θ ( rrΘ(N/log(N))?rΘ(N)

Una presentación de Carl Pomerance en " El orden multiplicativo mod en promedion " 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 )rO(N/log(N))NNrO(N/log(N))N o r O ( rO(N))?rO(N)

(Nota: hay una pregunta relacionada sobre factorización genérica versus factorización RSA)

Martin Schwarz
fuente

Respuestas:

17

N=pqrϕ(N)=lcm(p1,q1)p1=2pq1=2qp,qrpqN/4pp=2p+1pp

NN=pqrO(N)rO(N)

Peter Shor
fuente