Question

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

Answer 1

Let p and q be two prime number that generated the modulus parameter n in RSA cryptosystem

n = p*q = 3007

φ(n) = φ(p*q) = (p - 1)*(q - 1) = 2880

p*q - p - q + 1 = 2880

3007 - p - q + 1 = 2880

p + q = 128

p + 3007/p = 128

p² - 128p + 3007 = 0

p = 31 or p = 97

if p = 31 then q = 97 and vice versa

Hence answer is 97

Alternate Method:

n = p*q = 3007

From question it is clear that one prime number is less than 50

Prime number less than are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Now find which prime number will give remainder 0 on division with 3007

3007%31 = 0

3007/31 = 97

Tips to generate prime number:

Prime number is multiple of (6k ± 1) (except 2 and 3) where k is natural number but vice versa is not true