actually in rsa algorithm this happens:
two distinct prime numbers are choosen
then n=p*q is calculated
Compute φ(n) = (p – 1)(q – 1), where φ is Euler's totient function.
Choose an integer e such that 1 < e < φ(n) and greatest common denominator of (e,φ(n)) = 1, i.e. e and φ(n) are coprime.
e is released as the public key exponent.
e having a short bit-length and small Hamming weight results in more efficient encryption - most commonly 0x10001 = 65537. However, small values of e (such as 3) have been shown to be less secure in some settings.
Determine d = e–1 mod φ(n); i.e. d is the multiplicative inverse of e mod φ(n).
This is more clearly stated as solve for d given (d*e)mod φ(n) = 1
This is often computed using the extended Euclidean algorithm.
d is kept as the private key exponent.
The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d which must be kept secret.
Alice transmits her public key (n,e) to Bob and keeps the private key secret. Bob then wishes to send message M to Alice.
He first turns M into an integer m, such that 0 < m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to
c = me (mod n).
This can be done quickly using the method of exponentiation by squaring. Bob then transmits c to Alice.
the speed actually depends on the key size
In practical applications, it is common to choose a small public exponent for the public key.
In fact, entire groups of users can use the same public exponent, each with a different modulus. (There are some restrictions on the prime factors of the modulus when the public exponent is fixed.)
This makes encryption faster than decryption and verification faster than signing.
With the typical modular exponentiation algorithms used to implement the RSA algorithm, public key operations take O(k^2) steps, private key operations take O(k^3) steps, and key generation takes O(k^4) steps, where k is the number of bits in the modulus.
``Fast multiplication'' techniques, such as methods based on the Fast Fourier Transform (FFT), require asymptotically fewer steps.
In practice, however, they are not as common due to their greater software complexity and the fact that they may actually be slower for typical key sizes.