6,926 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 _________

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

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

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

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

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.

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?

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

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