# Algorithms for encryptor in RSA

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.