# Does knowing the totient of a number help factoring it?

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.)
• If $n$ is not square-free, then $gcd(n, \phi(n))$ is a non-trivial factor. Sep 6, 2012 at 13:05
• @RossMillikan The question you link deals with the case when $n=p^a q^b$. So it truly gives a partial answer to this one, but not to the general case when $n$ has 3 or more prime factors.
– Petr
Sep 6, 2012 at 13:26
• If en.wikipedia.org/wiki/… is true, there are at least two numbers having same totient value. Sep 6, 2012 at 13:28

In fact, it is a well-known observation in cryptography that just knowing a multiple of $\phi(n)$ helps greatly in factoring $n$, regardless of the number of prime factors (if there's only one or two primes 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$ from $m$, 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 will necessarily be even, unless $n$ is trivially small.)

It will then be the case 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 the GCD $(b^t-1,n)$ will produce a non-trivial factor of $n$.

One simply has to randomly try different values of $b$ (the expected number of tries 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 all the prime factors of $n$, just keep repeating the process (we still have a multiple of $\phi$ for each of factors found above).

• Why the downvote? This is the only actual answer to the question. Jun 19, 2013 at 4:05
• This answer doesn't explain how to compute the Carmichael function Apr 22 at 11:04
• @BoltonBailey If you read the answer, it doesn't actually need to compute the Carmichael function. The fact that $t$ exists is all you need to run the computation, because the number of choices of $t$ is very small, you can try each of them and one of them is "guaranteed" to work (bearing in mind there is some non-determinism in the algorithm). Apr 23 at 0:49
• @BoltonBailey Good question, yes actually I should have said the expected number of tries is bounded, which is even better than polynomial. I think it in the worst case that there are only two prime factors $p,q$ then the expected number of trials is $4$, and if there are more primes, then it should be smaller as there are more pathways to success. Apr 24 at 4:38
• @BoltonBailey And yes, I use base as a standard term of art as this process is very similar to Fermat primality testing (and Miller-Rabin which is an especially close relative to the idea in this post). Apr 24 at 4:39

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.

• I'm assuming OP meant you know $n$ and $\phi(n)$. If you know $pq$ and $(p-1)(q-1)$, you can find $p+q$ and hence find $p$ and $q$. Sep 6, 2012 at 13:16
• @ThomasAndrews: that was the point of my saying "if you already know it is a product of two primes". If you don't know that, it doesn't help. I added a few words. Sep 6, 2012 at 13:19
• @RossMillikan If we don't know that $n=pq$ we can still proceed the same way to compute $p$ and $q$. If the computation succeeds and $pq=n$ then we have the result, otherwise we at least know that $n$ has more prime factors than 2.
– Petr
Sep 6, 2012 at 13:23
• Does it help that the prime factors of $p-1,q-1,r-1$ are all likely to be orders of magnitude smaller than $p$, $q$, and $r$? If you then invest in factoring $\phi(n)$, then you have a finite number of combinations of those factors to check to see if they correspond to a factorization $pqr$. Maybe this is not efficient. I wonder what the statistics are on the size of primes dividing $\phi(n)$ versus of those dividing $n$. Jun 19, 2013 at 5:20

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