Fast factorization

Question

For a given number n (we know that n = p^a * q^b, for some prime numbers 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 have to be very fast. It seems to be very hard problem and I completely don't know how to use φ(n).

How to approach this?

Answer 1

For n = p^a * q^b, the totient is φ(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), thus you have x = p*q = n/gcd(n,φ(n)) and y = p+q = n/gcd(n,φ(n)) + 1 - φ(n)/gcd(n,φ(n)). Then finding p and q is simple: y^2 - 4*x = (q-p)^2, so q = (y + sqrt(y^2 - 4*x))/2, and p = y-q. Then finding the exponents a and b is trivial.

In the second case, n/gcd(n,φ(n)) = q. Then you can easily find the exponent b, dividing by q until the division leaves a remainder, and thus obtain 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^a-z). Finding the exponent a is again trivial.

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

For that, you need a decent primality test. Or you can first suppose that you have case 1, and if that doesn't work out, conclude that you have case 2.

Answer 2

Try working out what n / (n - φ(n)) is.

Follow up:

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