Does knowing the totient of a number help factoring it? [duplicate]

Question

Possible Duplicate:
Factoring a number $p^a q^b$ knowing its totient

Edit: The quoted question addresses only numbers of the form $p^a q^b$, I asked a general question for arbitrary $n$.

---

If $n$ is a prime or a product of 2 primes then knowing its totient $\varphi(n)$ allows us immediately to find the prime factorization of $n$.

How about a general case? Does knowing $\varphi(n)$

1. give us a way how to find the prime factorization of $n$,
2. help as find a prime factor of $n$, or at least
3. help at in finding any factor of $n$? ^{(This turns out to be obvious.)}

Answer 1

In fact, it is a well-known observation in cryptography that just knowing a multiple of $\phi(n)$ helps greatly in factoring it regardless of the number of prime factors (if there's only one prime dividing $n$ then this has already been covered).

Suppose $m$ is a multiple of $\phi(n)$. Then if you factor out enough powers of $2$, there must exist a divisor $t = m/(2^r)$ such that $\lambda(n) \mid 2t$ but $\lambda(n) \nmid t$. (Here, $\lambda(n)$ is the Carmichael function, which is even unless $n$ is trivially small.)

It will then happen that for some bases $b$, $b$ will be a quadratic residue for some prime $p \mid n$ but not for a different $q \mid n$. In this case, taking $(b^t-1,n)$ will produce a non-trivial factor of $n$.

One simply has to randomly try different values of $b$ (the expectation is finite), as well as different choices of $t$ (there are at most $\log(n)$ possibilities, and one can use successive squaring to efficiently cover them).

To get prime factors of $n$, just repeat the process (we still have a multiple of $\phi$ for both of those factors).

Answer 2

If $p^e$ divides $n$ then $p^{e-1}$ divides $\phi(n)$.

Answer 3

In the case of a prime, you can just observe that $\phi(n)=n-1$ to know it is prime. If $n=pq$ is a product to two primes, $\phi(n)=(p-1)(q-1)$, which you still need to factor. If you already know it is the product of two primes, you can use $\phi(n)=n-p-q+1$ to get $p+q$ as a second equation. As $\phi(n)$ has at least a couple factors of $2$ and may have other small factors, it will be somewhat smaller and can be easy to factor. Hagen von Eitzen makes a good point in the comment. If $n=pqr$, all prime, $\phi(n)=(p-1)(q-1)(r-1)$ and I don't see a good way to make headway except looking for small factors.