I am using the RSA crytposytem. I have $p$, $q$ and hence $n$ and $\phi$ however I don't understand how to get $e$ such that $gcd(e,\phi)=1$

Many thanks

  • 2
    $\begingroup$ That's covered here. $\endgroup$
    – fgrieu
    Commented Nov 30, 2014 at 19:31
  • 1
    $\begingroup$ @fgrieu Should we hit the close button? $\endgroup$
    – Maarten Bodewes
    Commented Dec 1, 2014 at 11:52

1 Answer 1


You need to choose e such that it is co-prime relative to PHY(n). Since you do not want to get involved in factorization of PHY(n), the best way is to choose e randomly, and better let it be a non even prime. Common values are 2^16+1, 3, etc. Most of the primes you choose will have GCD(e,PHY(n))=1.


Not the answer you're looking for? Browse other questions tagged or ask your own question.