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.