Fast factorization

Question

For a given number n (we know that n = p ^ a * q ^ b for some primes p, q and some integers a, b) and a given number φ (n) ( http://en.wikipedia.org / wiki / Euler% 27s_totient_function ) find p, q, a and b.

The catch is that n and φ (n) have about 200 digits, so the algorithm should be very fast. This seems to be a very difficult problem, and I don't completely know how to use φ (n).

How to do it?

Answer 1

For n = p^a * q^b , the totem φ(n) = (p-1)*p^(a-1) * (q-1)*q^(b-1) . Without loss of generality, p < q .

So gcd(n,φ(n)) = p^(a-1) * q^(b-1) if p does not divide q-1 and gcd(n,φ(n)) = p^a * q^(b-1) if p divides q-1 .

In the first case, we have n/gcd(n,φ(n)) = p*q and φ(n)/gcd(n,φ(n)) = (p-1)*(q-1) = p*q + 1 - (p+q) , so you have x = p*q = n/gcd(n,φ(n)) and y = p+q = n/gcd(n,φ(n)) + 1 - φ(n)/gcd(n,φ(n)) . Then the search for p and q is simple: y^2 - 4*x = (qp)^2 , therefore q = (y + sqrt(y^2 - 4*x))/2 and p = yq . Then finding the exponents a and b trivial.

In the second case, n/gcd(n,φ(n)) = q . Then you can easily find the exponent b divisible by q until the division leaves a remainder, and thus get p^a . Dividing φ(n) by (q-1)*q^(b-1) gives you z = (p-1)*p^(a-1) . Then p^a - z = p^(a-1) and p = p^a/(p^az) . The search for exponent a is trivial again.

So it remains to decide in which case you have. You have case 2 if and only if n/gcd(n,φ(n)) is simple.

To do this, you need a decent test for compliance. Or you can first assume that you have case 1, and if that does not work, conclude that you have case 2.

Answer 2

Try to figure out what n / (n - φ (n)) is.

Following actions:

n / (n - φ (n)) = pq. You just keep dividing n by pq.