Search code examples
encryptionnumbersrsacomputation-theorynumber-theory

In RSA encryption algorithm, Can we find P and Q, if we have totient of N

Totient(N) is a product of (P-1)(Q-1) and (P-1),(Q-1) will not be prime after taken 1 from them and multiple factors can be obtained? Is it true? Or can we find P and Q if we have totient of N?

Solution

  • Since only even prime is 2, rest of primes are odd. Therefore $p-1$ is an even number that can at least has 2 as a divisor.

    For the second part of your questions; What you do is playing with the equations;

    φ(n)=(p−1)(q−1)=pq−p−q+1=(n+1)−(p+q)

    (n+1)−φ(n)=p+q

    (n+1)−φ(n)−p=q

    and n=pq to obtain this quadratic formula.

    p2−(n+1−φ(n))p+n=0

    For more details and an example see; Why is it important that phi(n) is kept a secret, in RSA?