In RSA we denote encryptor as $E$ such that: $$\gcd(E,\phi(p,q))=1\tag{where $p,q$ are primes}$$

I know if for all prime factors $c$ of $\phi(p,q)$, $c \not\mid E$, that we can choose this $E$ as a encryptor, since in this case gcd is $1$.

What I did is for example: $$p=331,q=233,\phi(p,q)=(331-1)\cdot(233-1)=76560$$ Since $76560=2^4\cdot3\cdot5\cdot11\cdot29$, the smallest $E$ that would work is next prime after $5$ which is $7$.

Basicly, this is like looping though all the primes $P=\{2,3,5,7\cdots\}$, if it's not in the prime factor of $\phi(p,q):F=\{2,3,5,11,29\}$, then it's a valid choice of $E$.

So we can denote the smallest $E$ as the following: $$\min(P\cap F^c)$$

  • This is the algorithm i'm using right now, is there better approaches to find such $E$ ?
  • And there are many choice of $E$, but I don't know smaller $E$ is better or larger $E$ is better, would there be any difference if I pick different $E$ in RSA ?

Any help or suggestion would be appreciated.


Normally we use $\gcd(e,\lambda(n))=1$ as the criterion, where $\lambda(n)$ is the Carmichael function of the modulus $n$, for $n=pq$ this equals the least common multiple of $p-1$ and $q-1$, almost always smaller than $\phi(pq)=(p-1)(q-1)$.

Also, $p$ and $q$ are normally chosen beforehand with the property that $p-1$ and $p+1$ have no small prime factors except (the unavoidable) $2$. This to avoid some attacks.

This means that choosing $e=3$ is then always possible, and this is OK when using proper OAEP padding etc and almost always $e=2^{16}+1$, which are both very efficient for encrypting. If not, try the next prime, e.g.

See the key generation section of the Wikipedia page for more info and references.

  • 3
    $\begingroup$ Maybe you should also add that, when using 3 in textbook RSA, cuberoot attack is also possible and many other attacks therefore we use RSA encryption with proper paddings like PKCS#1.5 and OAEP... $\endgroup$ – kelalaka Dec 16 '19 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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