3
$\begingroup$

I have solved a problem in Project Euler. My solution was based on the finding the all numbers whose Euler Totient value equals to $13!$

However, while I was working on the problem, I thought that: "Can I find an algorithm that tests whether the Euler Totient of a number equals to $13!$ ?" I know that finding $\phi(n)$ is as hard as factoring $n$. On the other hand, we can easily test whether a specific number is a factor or not.

We have probabalistic primality tests such as: Fermat's, Euler's, Miller-Rabin etc. We can test the primality of a number efficiently. Can we use same approach to test "Is $\phi(n)$ equals to specific number?"

We know that $a^{\phi(n)} \equiv 1\pmod n$ if $\gcd(a,n) = 1$ by Euler's Theorem. Can we use this congruence to test probabilistically whether the Euler Totient of a number equals to certain value like in primality tests mentality?

Or more generally, What is the most efficient way of testing whether the Euler Totient of a number equals to certain value?

$\endgroup$
3
  • 1
    $\begingroup$ Oops, I misread that as 13 exclamation point instead of 13 factorial, which makes the problem quite trivial. Nevertheless, you want a fast test whether $\varphi(n)=m$. May we assume that $n$ may be arbitrarily wild, but $m$ is nice and (as is the case with $m=13!$) we know the prime factorization of $m$? In that case, there is a simple upper bound for $n$ and we can easily find all prime factors of $n$ (namely, primes dividing $m$, and primes dividing some $d+1$ where $d\mid m$). $\endgroup$ Commented Feb 3 at 21:29
  • $\begingroup$ @HagenvonEitzen this still can turn to be an answer.. $\endgroup$
    – kelalaka
    Commented Feb 3 at 22:34
  • $\begingroup$ @Hagen von Eitzen Actually my question is more general. In 13! case, there is no problem to factor n whose Euler Totient equals 13! as you say. However, I'dont remember the exact count but there are potential prime factors for n more than 400. Even if I know the all potential factors, factoring n and computing phi(n) is not efficient as I would like. $\endgroup$
    – NB_1907
    Commented Feb 4 at 22:48

1 Answer 1

2
$\begingroup$

Yes, though it is not completely straightforward.

There is a tighter form of Euler's theorem for composite numbers that says that $a^{\lambda(n)}\equiv 1\pmod n$ for $(a,n)=1$ where $\lambda(n)$ is the Carmichael function. The Carmichael function always divides $\phi(n)$ but (for example) for odd composite numbers it is always less than $\phi(n)$. Therefore simply testing to see if $13!$ is a multiple of the order of random residues (and there there exist random residues where the order is exactly 13!) won't allow us to distinguish numbers where $\lambda(n)=13!$ but $\phi(n)>13!$.

However, a you note we can compute $\phi(n)$ if we can factor $n$ and it turns out that the numbers where $\phi(n)=13!$ are very easy to factor using a variant of Pollard's $p-1$ algorithm. Given a candidate non-prime $n$, we pick a random $a$ (we can check if $(a,n)=1$ and divide out a GCD is it is), raise it to the power $13!/1024$ modulo $n$ and there is a very good chance that the answer is not $\pm 1$ (we can even raise the odds by choosing $a$ with Jacobi symbol -1 mod $n$). Writing the answer as $x$ we compute $x^2, x^4, \ldots , x^{1024}\mod n$ by squaring. Eventually the sequence becomes all 1s (the last value is certainly 1) and the previous value is either -1 or a non-trivial square root of unity, say $y$ such that $y^2\equiv 1\pmod n$. In this case $\mathrm{GCD}(n,y\pm1)$ splits $n$ into two smaller numbers. The method recurses and I'll leave the details to you.

$\endgroup$
1
  • $\begingroup$ FYI. This answer is hard to follow... $\endgroup$
    – kelalaka
    Commented Feb 3 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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