Algoritmo para encontrar números primos de forma específica

Question

Dado el número natural $n$ que está en forma $p^2 \cdot q^2$ con $p$ , $q$ números primos. $(n)$ Describa un algoritmo rápido (tiempo polinómico) que calcule el $p$ y $q$ Aplique su algoritmo para calcular el $p$ , $q$ cuando $n=34969$ y $(n)=29920$

Encontré este problema en un concurso matemático sobre criptografía.intenté encontrar una solución solo y en internet y no llegué a ninguna parte, ¿se puede encontrar una solución?

Answer 1

Pista: $$\phi(n) = n^2 - n(p+q) - pq$$

Answer 2

Desde $n$ es un cuadrado perfecto, $pq = \sqrt{n}$ . Ahora, en cuanto a la $\phi$ función: $$ \phi(p^2 q^2) = \phi(p^2)\phi(q^2) = (p - 1)(q - 1)pq$$

Así, $$\dfrac{\phi(n)}{\sqrt{n}} = (p - 1)(q - 1) = pq - p - q + 1$$ Y así, se obtiene: $$\sqrt{n} - \dfrac{\phi(n)}{\sqrt{n}} + 1= p + q = p + \dfrac{\sqrt{n}}{p}$$ Multiplica ambos lados por $-p$ : $$p^2 - p\left(\sqrt{n} - \dfrac{\phi(n)}{\sqrt{n}} + 1\right) + \sqrt{n} = 0$$

Probemos tu ejemplo. Desde $n = 34969$ y $\phi(n) = 29920$ entonces $\sqrt{n} = 187$ y la ecuación que tenemos que resolver para $p$ es: $$p^2 - p\left(187 - \dfrac{29920}{187} + 1\right) + 187 = 0$$ Si simplificamos: $$p^2 - 28p + 187 = 0$$ Las soluciones son $p = 11$ y $p = 17$ . En realidad, debido a la relación simétrica entre $p$ y $q$ en nuestra ecuación anterior, estas dos soluciones para $p$ resulta ser la solución para el par $(p, q)$ . Te darías cuenta de que $pq = 187$ si asignamos $p = 11$ y $q = 17$ .

Por lo tanto, un algoritmo eficiente es resolver la ecuación cuadrática. La solución para el par $(p, q)$ no es más que las dos raíces de la ecuación. Esto es $\mathcal{O}(1)$ .