Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)
share|improve this question
1  
If $n$ is not square-free, then $gcd(n, \phi(n))$ is a non-trivial factor. –  Hagen von Eitzen Sep 6 '12 at 13:05
1  
@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 Pudlák Sep 6 '12 at 13:26
    
If en.wikipedia.org/wiki/… is true, there are at least two numbers having same totient value. –  lab bhattacharjee Sep 6 '12 at 13:28
add comment

3 Answers

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.

share|improve this answer
    
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$. –  Thomas Andrews Sep 6 '12 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. –  Ross Millikan Sep 6 '12 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 Pudlák Sep 6 '12 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$. –  alex.jordan Jun 19 '13 at 5:20
add comment

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

share|improve this answer
add comment

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).

share|improve this answer
    
Why the downvote? This is the only actual answer to the question. –  Erick Wong Jun 19 '13 at 4:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.