retagged by
8,844 views
13 votes
13 votes
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 _________
retagged by

6 Answers

Best answer
22 votes
22 votes
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
edited by
34 votes
34 votes
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..
3 votes
3 votes
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$.
edited by
Answer:

Related questions

39 votes
39 votes
12 answers
1
26 votes
26 votes
6 answers
2
Arjun asked Feb 7, 2019
19,689 views
Consider that $15$ machines need to be connected in a LAN using $8$-port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum ...