7
$\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$ Sep 6, 2012 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, 2012 at 13:26
  • $\begingroup$ If en.wikipedia.org/wiki/… is true, there are at least two numbers having same totient value. $\endgroup$ Sep 6, 2012 at 13:28

3 Answers 3

16
$\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$
7
  • 1
    $\begingroup$ Why the downvote? This is the only actual answer to the question. $\endgroup$
    – Erick Wong
    Jun 19, 2013 at 4:05
  • $\begingroup$ This answer doesn't explain how to compute the Carmichael function $\endgroup$ Apr 22 at 11:04
  • $\begingroup$ @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). $\endgroup$
    – Erick Wong
    Apr 23 at 0:49
  • 1
    $\begingroup$ @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. $\endgroup$
    – Erick Wong
    Apr 24 at 4:38
  • 1
    $\begingroup$ @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). $\endgroup$
    – Erick Wong
    Apr 24 at 4:39
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$ Sep 6, 2012 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$ Sep 6, 2012 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, 2012 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$
    – 2'5 9'2
    Jun 19, 2013 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.