The Gateway to Computer Science Excellence
+10 votes
3.1k views
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 by Veteran (431k points)
edited by | 3.1k views
+12

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

5 Answers

+18 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
by Junior (641 points)
edited by
+1

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?

+29 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..
by (229 points)
0
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
Good explanation thanks.
+1 vote

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

 

by Boss (10.6k points)
+1 vote
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$.
by Active (1.9k points)
edited by
+1 vote

solving the quadratic equation

 

by (89 points)
reshown by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,374 answers
198,513 comments
105,289 users