Skip to main content
3 of 3
latex syntax
kelalaka
  • 49.5k
  • 12
  • 119
  • 205

Is phi-hiding assumption as hard as integer factorization?

Phi-hiding assumption can be simply stated as (wrt hardness)

It is difficult to find small factors of $\varphi(m)$ where $m$ is a number whose factorization is unknown and $\varphi$ is Euler's totient function.

Is the hardness due to this assumption comparatively higher than than the hardness of integer factorization?

My intuition says that finding prime factors of $\varphi(m)$ is simpler than finding the prime factors of $m$. So I believe that the hardness of the phi-hiding assumption is at most equal to the hardness of integer factorization.

Fateh
  • 107
  • 5