GATE CS 2019 Q54 — Concept of Layering: OSI and TCP/IP Protocol Stacks

In the RSA cryptosystem, the public modulus $n$ is the product of two distinct prime numbers, $p$ and $q$:

$$n = p \cdot q = 3007$$

Euler's totient function $\phi(n)$ for the product of two primes is given by:

$$\phi(n) = (p-1)(q-1)$$

Expanding this expression, we get:

$$\phi(n) = p \cdot q - (p+q) + 1$$

Substitute the given values $n = 3007$ and $\phi(n) = 2880$ into the equation:

$$2880 = 3007 - (p+q) + 1$$

$$2880 = 3008 - (p+q)$$

$$p+q = 3008 - 2880 = 128$$

We now have a system of two equations:

1. $p + q = 128$
2. $p \cdot q = 3007$

These can be solved by forming a quadratic equation with roots $p$ and $q$:

$$x^2 - (p+q)x + pq = 0$$

$$x^2 - 128x + 3007 = 0$$

Using the quadratic formula:

$$x = \frac{-(-128) \pm \sqrt{(-128)^2 - 4 \cdot 1 \cdot 3007}}{2}$$

$$x = \frac{128 \pm \sqrt{16384 - 12028}}{2}$$

$$x = \frac{128 \pm \sqrt{4356}}{2}$$

Since $\sqrt{4356} = 66$:

$$x = \frac{128 \pm 66}{2}$$

This gives two possible values for the prime factors:

$$x_1 = \frac{128 + 66}{2} = 97$$

$$x_2 = \frac{128 - 66}{2} = 31$$

Thus, the prime factors of $3007$ are $31$ and $97$.

The prime factor of $n$ which is greater than $50$ is 97.