6
$\begingroup$

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

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

$\endgroup$
1
  • 1
    $\begingroup$ Why the downvote? This is the only actual answer to the question. $\endgroup$ – Erick Wong Jun 19 '13 at 4:05
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Sep 6 '12 at 13:16
  • 1
    $\begingroup$ @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. $\endgroup$ – Ross Millikan Sep 6 '12 at 13:19
  • 1
    $\begingroup$ @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. $\endgroup$ – Petr Sep 6 '12 at 13:23
  • $\begingroup$ 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$. $\endgroup$ – alex.jordan Jun 19 '13 at 5:20
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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