Knowing large prime factor$(r > n^{1/4})$ of $\phi(n)$ can easily factorize n and hence learn $\phi(n)$.

If we have knowledge on all small prime factors $(2< r_i << n^{1/4})$ of $\phi(n)$ then, is there any efficient way to factorize $n$ and $\phi(n)$?

Note: $n$ is an RSA number

  • 2
    $\begingroup$ What is pi(n)? Normally $\pi(n)$ denotes the number of primes $\le n.$ Do you mean $\varphi(n)?$ Since a RSA number $n$ is often written as $n=pq,$ it would be less confusing if you use another symbol for your factor. $\endgroup$ Sep 27, 2018 at 10:17
  • 4
    $\begingroup$ In general, no; if $p, q$ are both safe-primes, then the product all the small prime factors of $\phi(n) $ is $4$; that knowledge doesn't help very much... $\endgroup$
    – poncho
    Sep 27, 2018 at 17:53


Your Answer

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