Question

p = 13

q = 37

Totient = 432

n = 481

e = 19

d = 91

public key: n = 481, e = 19

private key: n= 481, d = 91

Except 1, explain any other prime number less than e which cannot be used to generate d? What are those number and why they cannot be used?

Answer 1

Ans: 3 and 5 numbers can't be selected as e

Here p=13 , q=37 and n=p*q=13*37=481 and Totient=(p-1)*(q-1)=432

And given that e=19 and d=91

now,

Public key : n=481 ,e=19

Private key: n=481 , d=91

Now,

The prime numbers less than e=19 are 2,3,5,7,11,13,17

For selecting e , there are two conditions i.e, GCD(e,Totient)=1 and 1<e<Totient

second condition is not required here, because here we are taken prime numbers upto 20 only,

Now we have to check for the numbers which satisfy GCD(e,Totient)=1

Here 2 can't be selected because GCD(2,432)=2

3 can't be selected because GCD(3,432)=3

5 can be selected because GCD(5,432)=1

7 can be selected because GCD(7,432)=1

11 can be selected because GCD(11,432)=1

13 can be selected because GCD(13,432)=1

17 can be selected because GCD(17,432)=1

Therefore,

3 and 5 are the numbers which can't be selected as e