GATE CSE 2019 | Question: 54

Question

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

Comments

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

$n=pq$

---

$2880=pq-p-q+1$

$128=p+q...................(1)$

$3007=pq.....................(2)$

---

$Using\ (1)\ \&\ (2)$

$q^2-128q+3007$

$Roots:$

$\\ \dfrac{-b\pm \sqrt{b^2-4ac}}{2a}\\ \\ \dfrac{128\pm \sqrt{(128)^2-4\times1\times3007}}{2}\\ \\ \dfrac{128\pm66}{2}\\ \\ \dfrac{194}{2}=97\checkmark\ \&\ \dfrac{62}{2}=31$

---

This approach is well structured :)

---

I think this topic is no longer in the syllabus from this year...

Answer 1

solving the quadratic equation

 

Answer 2

I am so proud to say that I solved this question correctly

It is based on RSA public key encryption.

ɸ(n) = 2880, n=3007

What is the prime factor of n which is greater than 50

Approach

For faster resolution,

n=pq

start dividing 3007 by prime numbers 3,5,7,11,13,17,19,23,27,31,...

You will take 15 seconds to find out that 31 is a factor

now when you were dividing 3007 by 31 you will realise that you will get the other factor 97

as 3007/31 = 97

So the factor which was greater than 50 was 97