Es posible factor de forma eficiente un semiprime dado un poco-permutación relativos de los factores? Por ejemplo, supongamos que tenemos $n = p * q = 167653$; en este caso, $p = 359 = 101100111_2$ $q = 467 = 111010011_2$ están relacionados por el poco permutación $K = (2 4) (5 7)$. Si $K$ es conocido, puede $n$ ser descontado en el tiempo polinomio?
Respuesta
¿Demasiados anuncios?
Si K se compone de $k$ orden 2 distinto de swaps (como se sugiere en un comentario de Dan) y si $p,\ q$ $u$ bits de longitud (es decir, $u = \lceil \lg p \rceil$ donde $\lg x$ denota $\log_2 x$), a continuación, un ingenuo búsqueda puede realizarse en $\theta(3^k)$ tiempo, como se señala a continuación. Sólo si $k$ es pequeña y no depende de la $u$ (es decir, se $O(1)$ e no $O(u)$) sería ingenuo búsqueda de ser útil. No sé si la forma especial de los números ayude en todo moderno entero rápido algoritmo de factorización, y en la siguiente meramente de trabajo fuera de la aritmética de ingenuo cuando la búsqueda es factible.
El $\theta(3^k)$ unido (vs $2^{2k-1}$ sugerido por Jyrki) surge como sigue. Tenemos $n = p\cdot q = (r-h)(r+h)$ donde $p,\ q$ son primos, $r=(p+q)/2$, e $h$ es la mitad de un delta de la forma dictada por K. Cada delta es la suma de $k$ términos. El plazo para K-elemento $(a\ b)$ con LSB numerado como el bit 1 tiene una de tres formas: 0, $2^a-2^b$ o $2^b-2^a$. Por lo tanto, $3^k$ sumas de términos $t_1+t_2+...t_k$ son posibles. La mitad de la serie son los aspectos negativos de la otra mitad, y no necesitan ser considerados. El uso ingenuo de búsquedas (dividir por números primos, frente a las pruebas de $3^k/2$ posible deltas) el mismo número de pruebas surgen cuando $\sqrt p / \ln\sqrt p = 3^k/2$, o [update 1] $k\approx u \lg2/(2\lg3) +\lg2/\lg3\approx 0.31\cdot u+0.63$, que es cuando aproximadamente 2/3 de los bits de $p,\ q$ cambio de lugares.
Por supuesto, las pruebas que resolver las ecuaciones cuadráticas son más caros que los que solo hay que dividir con el resto, pero la idea general sigue siendo que $k$ debe $O(1)$ de viabilidad.
Actualización 2: Anteriormente yo inadvertencia utilizado $n$ dos maneras, como se menciona en los comentarios a continuación y se ilustra en mi primera respuesta. Ahora $n = p\cdot q$ $u$ = número de bits en el p.
