Reducción de productos primos de factorización a productos enteros de factoring (en el caso promedio)

Mi pregunta es acerca de la equivalencia de la seguridad de varias funciones unidireccionales candidatas que pueden construirse en función de la dureza del factoring.

Asumiendo el problema de

FACTORIZACIÓN: [Dado para primos aleatorios P , Q < 2 n , encuentre P , Q. ]$N = PQ$$P, Q < 2^n$$P$$Q$

no se puede resolver en tiempo polinómico con probabilidad no despreciable, la función

PRIME-MULT: [Dada la cadena de bits como entrada, use x como semilla para generar dos primos aleatorios P y Q (donde las longitudes de P , Q son solo polinomialmente más pequeñas que la longitud de x ); entonces salida P Q ]$x$$x$$P$$Q$$P$$Q$$x$$PQ$

se puede demostrar que es unidireccional.

Otra función unidireccional candidata es

INTEGER-MULT: [Dados enteros aleatorios como entrada, salida A B. ]$A, B < 2^n$$A B$

INTEGER-MULT tiene la ventaja de que es más fácil de definir en comparación con PRIME-MULT. (Observe en particular que en PRIME-MULT, existe la posibilidad (aunque afortunadamente insignificante) de que la semilla no genere P , Q que son primos).$x$$P, Q$

Al menos en dos lugares diferentes (Arora-Barak, Computational Complexity, página 177, nota 2) y ( Notas de lectura de Introducción a la Criptografía de Vadhan ) se menciona que INTEGER-MULT es unidireccional suponiendo una dureza promedio de factorización. Sin embargo, ninguno de estos dos da la razón o una referencia para este hecho.

Entonces la pregunta es:

¿Cómo podemos reducir la factorización de tiempo polinomial de con probabilidad no insignificante a invertir INTEGER-MULT con probabilidad no insignificante?$N = PQ$

Aquí hay un posible enfoque (que como veremos NO funciona): dado , multiplique N por un entero aleatorio mucho más largo (aunque polinomialmente) A ' para obtener A = N A ' . La idea es que A ' es tan grande que tiene un montón de factores primos de tamaño aproximadamente igual a P , Q , de manera que P , Q no "se destacan" entre los factores primos de A . Entonces A tiene aproximadamente la distribución de un número entero aleatorio uniforme en un rango dado (digamos [ $N = PQ$$N$$A'$$A = NA'$$A'$$P, Q$$P, Q$$A$$A$ ). Luego elija el entero B al azar del mismo rango [ 0 , 2 n - 1 ] .$[0,2^n-1]$$B$$[0,2^n-1]$

Ahora, si un inversor para INTEGER-MULT puede, dado , con alguna probabilidad encontrar A ′ , B ′ < 2 n tal que A ′ B ′ = A B , la esperanza es que uno de A ′ o B ′ contenga P como un factor y el otro contiene Q . Si ese fuera el caso, podemos encontrar P o Q tomando mcd de A ' con N = P Q .$AB$$A', B' < 2^n$$A'B' = AB$$A'$$B'$$P$$Q$$P$$Q$$A'$$N = PQ$

El problema es que el inversor puede elegir separar los factores primos, por ejemplo, colocando los factores pequeños de en A ' y los grandes en B ' , de modo que P y Q terminen en A ' o ambos en B ′ .$AB$$A'$$B'$$P$$Q$$A'$$B'$

¿Hay otro enfoque que funcione?

Esto no es realmente una respuesta, pero arroja algo de luz sobre la dificultad de demostrar tales reducciones.

$\mathcal{A}$$n^{-c}$$c \in \mathbb{N}$$n$$\mathcal{A}'$$\mathcal{A}$$n$$n^{-d}$$d \in \mathbb{N}$

$\mathcal{A}^*$$N$ $N = PQR$$P$$Q$$n/4$$R$$n/2$$N$$PQ$$R$$\mathcal{A}^*$$n$$\mathcal{A}^*$

$k$

$2^k / \ln(2^k) - 2^{k-1} / \ln(2^{k-1}) = \Theta(2^k / k)$

$n$

$\frac{\Theta(2^{n/4} / (n/4))^2 \cdot \Theta(2^{n/2} / (n/2))}{2^{n-1}} = \Theta(n^{-3})$

$n$

$\mathcal{A}'$$\mathcal{A}^*$$n$$n^{-d}$$d \in \mathbb{N}$

$\mathcal{A}^*$$PQ$