¿Conocer el concepto de un número ayuda a factorizarlo?

Question

Edit: El citado pregunta se refiere sólo a los números de la forma $p^a q^b$ le pedí a una pregunta general para arbitrario $n$.

---

Si $n$ es un primo, o un producto de 2 números primos y después de conocer su totient $\varphi(n)$ permite que nosotros de inmediato para encontrar la factorización prima de $n$.

Cómo sobre un caso general? Hace saber $\varphi(n)$

1. nos dan una manera de cómo encontrar la factorización prima de $n$,
2. ayudar a encontrar un primer factor de $n$, o al menos
3. ayuda a encontrar cualquier factor de $n$? ^{(Esto resulta obvio.)}

Answer 1

De hecho, es bien conocida la observación en la criptografía que acaba de conocer a un múltiplo de $\phi(n)$ ayuda enormemente en contar con él, sin importar el número de factores primos (si sólo hay un primer dividiendo $n$, entonces esto ya ha sido cubierto).

Supongamos $m$ es un múltiplo de a $\phi(n)$. Entonces, si el factor de suficientes poderes de $2$, debe existir un divisor $t = m/(2^r)$ tal que $\lambda(n) \mid 2t$ pero $\lambda(n) \nmid t$. (Aquí, $\lambda(n)$ es el Carmichael función, que es incluso menos $n$ es extremadamente pequeño.)

Entonces ocurrir que para algunas bases $b$, $b$ va a ser un residuo cuadrático para algunos prime $p \mid n$ pero no para otro $q \mid n$. En este caso, teniendo en $(b^t-1,n)$ producirá un no-trivial factor de $n$.

Uno simplemente tiene que aleatoriamente probar diferentes valores de $b$ (la expectativa es finito), así como diferentes opciones de $t$ (existen en la mayoría de las $\log(n)$ posibilidades, y uno puede usar sucesivas cuadrado para cubrir en forma eficiente).

Para obtener los factores primos de a $n$, sólo tiene que repetir el proceso (todavía tenemos un múltiplo de $\phi$ tanto de los factores).

Answer 2

En el caso de un primo, se puede observar que $\phi(n)=n-1$ saber que es primo. Si $n=pq$ es un producto de dos números primos, $\phi(n)=(p-1)(q-1)$, que todavía se necesita un factor. Si ya saben que es el producto de dos números primos, puede utilizar $\phi(n)=n-p-q+1$ conseguir $p+q$ como la segunda ecuación. Como $\phi(n)$ tiene al menos un par de factores de $2$ y puede tener otros pequeños factores, va a ser un poco más pequeña y puede ser fácil factor. Hagen von Eitzen hace un buen punto en el comentario. Si $n=pqr$, todos los primos, $\phi(n)=(p-1)(q-1)(r-1)$ y no veo una buena manera de avanzar, excepto en busca de pequeñas factores.

Answer 3

Si$p^e$ divide$n$ entonces$p^{e-1}$ divide$\phi(n)$.