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

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

---

ISN'T THIS OUT OF SYLLABUS

---

Can we skip cryptography topic now or should it still be done?

Answer 1

List all the prime numbers less than $50$.

$ 2,3,5,7,11,13,17,19,23,29,31,37,41,47 $

and start dividing $3007$ from last number and choose the quotient of the greatest number less than $50$ that divides $3007$ completely

$3007/31=97$ is the answer

Comments

Does this process come from checking prime or not? 

where we take sqrt(3007) = 54.83

so we list out primes less than 54 but here primes less than 50 is asked so start from 47?

And take the biggest one that divides 3007 bcs that gives closest no above 50 dividing 3007?

---

@Dharmendra Tiwari I think in list of prime number 43 is missing

Answer 2

Let n=p*q(since n is multiplication of two prime numbers)

n=3007

p*q=3007.............................................eq(1)

 Ø(n) =2880(given)

 Ø(n) = Ø(p) * Ø(q) =(p-1)*(q-1)

 Ø(n) =p*q-p-q+1=2880.......................eq(2)

Two equation and two variables, by solving these equations we can get p and q and see which one is greater than 50.

p+q-1=127

p+(3007/p)=128

p^2-128p+3007=0

Solving this equation we will get two values for p i.e. p=97 and p=31.

So 97 is the answer..

Comments

given a lot of time for this question in the exam...still unable to solve.

now it seems it was very easy. thanks for the solution:)

---

Good explanation thanks.

---

how do we know that  n is formed by multiplication of only two prime numbers? it can be more than that too?

and what is RSA cryptosystem?

Answer 3

........................ 

 

Answer 4

Given, $\Phi(n)$ = $2880$ & $\ n=3007 ,i.e, p*q=3007$

We know that $\Phi(n)$ = $\Phi (p*q)=\Phi (p)*\Phi (q)=(p-1)*(q-1)$

$=> 2880=(p-1)*(q-1)$

$=> 2880=p*q-p-q+1$

$=> 2880=3007-p-q+1$

$=> p+q=128$

Since $\large p , q$ are prime numbers in RSA algorithm, one of them can be $127, 113, 109, 107, 103, 101, 97,$.........

In exam hall,use calculator to divide 3007 with each of these numbers (starting from $127$ ) to find the prime factor. The whole process will take <3 minutes.

We will get the answer as $97$.

Answer 5

solving the quadratic equation

 

Answer 6

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