Factorización rápida

Question

Para un número dado n (sabemos que n = p^a * q^b, para algunos números primos p, qy algunos enteros a, b) y un número dado φ (n) (http://en.wikipedia.org/wiki/Euler%27s_totient_function) encuentra p, q, a y b.

El inconveniente es que ny φ (n) tienen unos 200 dígitos, por lo que el algoritmo debe ser muy rápido. Parece ser un problema muy difícil y completamente no sé cómo usar φ (n).

¿Cómo abordar esto?

Answer 1

Para n = p^a * q^b, el totient es φ(n) = (p-1)*p^(a-1) * (q-1)*q^(b-1). Sin pérdida de generalidad, p < q.

Así gcd(n,φ(n)) = p^(a-1) * q^(b-1) si p no divide q-1 y gcd(n,φ(n)) = p^a * q^(b-1) si p divide q-1.

En el primer caso, tenemos n/gcd(n,φ(n)) = p*q y φ(n)/gcd(n,φ(n)) = (p-1)*(q-1) = p*q + 1 - (p+q), por lo tanto usted tiene x = p*q = n/gcd(n,φ(n)) y y = p+q = n/gcd(n,φ(n)) + 1 - φ(n)/gcd(n,φ(n)). Luego, encontrar p y q es simple: y^2 - 4*x = (q-p)^2, entonces q = (y + sqrt(y^2 - 4*x))/2, y p = y-q. Entonces encontrar los exponentes a y b es trivial.

En el segundo caso, n/gcd(n,φ(n)) = q. Entonces puede encontrar fácilmente el exponente b, dividiendo por q hasta que la división deje un resto, y así obtener p^a. Dividiendo φ(n) por (q-1)*q^(b-1) le da z = (p-1)*p^(a-1). Luego p^a - z = p^(a-1) y p = p^a/(p^a-z). Encontrar el exponente a es nuevamente trivial.

Así que queda por decidir qué caso tienes. Tiene el caso 2 si y solo si n/gcd(n,φ(n)) es primo.

Para eso, necesitas una prueba de primalidad decente. O puede suponer primero que tiene el caso 1, y si eso no funciona, concluya que tiene el caso 2.

Answer 2

Intenta averiguar qué es n/(n - φ (n)).

seguimiento:

n/(n - φ (n)) = pq. Solo sigues dividiendo n por pq.