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 _________

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

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
+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?

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.

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
+1 vote

by (89 points)
reshown