Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For simplicity I choose two small primes for p and q.


Now we need to find the public key e, which has to be coprime with Φ(n). For small numbers like these it is trivial, but how can it be done when larger primes are chosen?

share|improve this question
up vote 1 down vote accepted

This is easy, just pick $e$ as prime larger than $\max(p,q)$. As $\phi(n) = (p-1)(q-1)$ it has only prime factors smaller than $q$ and $p$.

You can also do trial and error. If $e$ is prime, the gcd test is very fast. But it is technically not necessary to choose $e$ prime. Also note that key generation is not time critical.

However, often one starts with $e \in \{ 3,5,17,257,65537 \}$ which are special primes. Then one choose $q$ and $p$ appropriate. These exponents have computational benefits as they are of the form $2^k+1$. That makes computation of the $e$-th power fast. Note that there are attacks for small exponents, especially $e=3$. They are all related to bad implementations, i.e. padding and so on. The RSA-scheme itself is not affected.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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