RSA Algorithm key generation

Question

I'm currently struggling with RSA encryption algorythm.

My problem is located at the public/private key generation ,here are my steps:

 1. -Generate 2 prime numbers p, q with p > q and nbBits(p) == nbBits(q)
             using the miller-rabin algorythm this was done succesfully
 2. -compute n = p*q
 3. -compute fi(n) = (p-1)*(q-1)

Here comes the trouble : i need to find one integer e with q < e < fi(n). This integer needs to have some sort of primality.

My question being : does e has to be primal (cannot be divided by any number else than itself or 1) OR primal WITH fi(n) (gcd(e, fi(n)) = 1) OR both?

I really have some issues figuring that out (my source clearly states the Euclide algorythm(gcd) is needed, but since English isn't my native language i have some trouble with mathematical English)

Probably a dumb question, but i couldn't find a clear explanation of it (at least clear enough for me).

Thanks for reading, even more for answering.

Answer 1

The encryption exponent e needs to be coprime with phi(n), that is, gcd(e,phi(n)) = 1. This condition is necessary because otherwise, you won't be able to construct (via Euclid's extended algorithm) an exponent d (the decryption exponent) such that e*d = 1 mod phi(n).