Entero de la factorización de conocimiento adicional de $p \oplus q$

Question

Dadas dos desconocidos grandes números primos $p$$q$, podemos de manera eficiente el factor de $n=pq$ si que, además, sabe $p \oplus q$ (XOR bit a bit de los números primos)?

EDIT: he implementado el algoritmo descrito en el poncho de la respuesta en este código Python.

Answer 1

Creo que podemos, de hecho, el factor de forma eficiente.

Considere la posibilidad de este algoritmo de factorización; podemos hacer un seguimiento del conjunto de $k$ los valores de los bits $p_k, q_k$ que satisfacer $p_k \times q_k \equiv n \bmod 2^k$; para cada iteración, intentamos extender $p_k, q_k$ por un bit, la generación de 0-4 posibles soluciones $p_{k+1}, q_{k+1}$ que satisfacer $p_{k+1} \times q_{k+1} \equiv n \bmod 2^{k+1}$.

Ahora, cuando se aplica este enfoque a la norma de la factorización de método, se produce un error miserable; resulta que siempre habrá 2 soluciones a paso $k+1$ por cada solución en el paso $k$ (y por lo tanto, tenemos un tiempo exponencial de la solución).

Sin embargo, si añadimos la restricción adicional de que el $p_k \oplus q_k = m$ (donde $m$ es el valor conocido de $p \oplus q$, esto reduce drásticamente el número de soluciones intermedias. Yo creo que lo que va a pasar es que, cuando estamos en un $p_k, q_k$, la mitad del tiempo, habrá 0 soluciones para el paso $k+1$ (y por lo tanto, podemos eliminar esa rama del árbol), y la mitad del tiempo, habrá 2 soluciones. Lo que esto nos da es bastante lento crecimiento de la cantidad de soluciones en general como aumentar el $k$; esto hace que sea totalmente factible para llegar a $k = \log_2{n}$ (y, en este punto, podemos comprobar las soluciones intermedias directamente)