GATE CS 2019 Q.64 (CS Q.54): Application Layer: DNS, HTTP, SMTP, FTP

In an RSA cryptosystem, the value of the public modulus parameter $n$ is 3007. If it is also known that $\phi(n) = 2880$ , where $\phi()$ denotes Euler's Totient Function, then the prime factor of $n$ which is greater than 50 is ________.

Your answer

Official answer and solution

Official answer: 97
From: Official GATE 2019 answer key

Solution

Set up a quadratic equation for the two prime factors $p$ and $q$ of $n$ using $n = pq$ and $\phi(n) = (p-1)(q-1)$ , solve for the roots, and select the prime greater than 50.

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

n = p \cdot q = 3007

Euler's totient function for the product of two primes is:

\phi(n) = (p - 1)(q - 1) = pq - (p + q) + 1 = n - (p + q) + 1

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

2880 = 3007 - (p + q) + 1 \implies p + q = 3008 - 2880 = 128

Now we have a system of two symmetric equations:

p + q = 128, \quad pq = 3007

The primes $p$ and $q$ are the roots of the quadratic equation:

t^2 - 128t + 3007 = 0

The discriminant of this quadratic equation is:

\Delta = (-128)^2 - 4(1)(3007) = 16384 - 12028 = 4356

Since $\sqrt{4356} = 66$ , the roots are:

t = \frac{128 \pm 66}{2}

This yields:

p = \frac{128 + 66}{2} = \frac{194}{2} = 97

q = \frac{128 - 66}{2} = \frac{62}{2} = 31

Both 97 and 31 are prime numbers, and $97 \times 31 = 3007$ .

The question asks for the prime factor of $n$ which is greater than 50. Since $97 > 50$ , the answer is 97.

Final answer

Common trap

Entering 31 instead of 97 because 31 is the smaller root, ignoring the condition 'greater than 50'.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2019 Computer Science and Information Technology (CS)
Question: 64 of 65, printed as CS Q.54
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source