in Computer Networks edited by
6,926 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 _________
in Computer Networks edited by
by
6.9k views

3 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$

23
23
This approach is well structured :)
0
0
I think this topic is no longer in the syllabus from this year...
1
1

6 Answers

20 votes
20 votes
Best answer
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

1 comment

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?

2
2
32 votes
32 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 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:)
0
0
Good explanation thanks.
0
0

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?

0
0
3 votes
3 votes

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

 

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