In an RSA cryptosystem, the value of the public modulus parameter 𝑛 is 3007. If it is also known that φ(𝑛) = 2880, where φ() denotes Euler’s Totient Function

Q. In an RSA cryptosystem, the value of the public modulus parameter 𝑛 is 3007. If it is also known that φ(𝑛) = 2880, where φ() denotes Euler’s Totient Function, then the prime factor of 𝑛 which is greater than 50 is

Ans:

Given,

n = p * q = 3007  … … (1)

And,

φ(n) = (p – 1) * (q – 1) = 2880 … … (2)

→ pq – p – q + 1 = 2880

→ 3007 – p – q + 1 = 2880

→ p + q = 128 ……(2)

Using equation (1) and (2),

→ (3007 / q) + q = 128

→ q2 – (128*q) + 3007 = 0

On solving the above equation:

q = 31, 97 

97 is greater than 50.