been computed. In the original RSA paper, the Euler totient function is used instead of for calculating the private exponent . Since is always divisible by , the algorithm works as well. The possibility of using Euler totient function results also from Lagrange's theorem applied to the multiplicative group of integers modulo pq. Thus any satisfying also satisfies . However, computing modulo will sometimes yield a result that is larger than necessary (i.e. ). Most of the implementations of RSA will accept exponents generated using either method (if they use the private exponent at all, rather than using the optimized decryption method based on the Chinese remainder theorem described below), but some standards such as FIPS 186-4 may require that . Any "oversized" private exponents not meeting this criterion may always be reduced modulo to obtain a smaller equivalent exponent. Since any common factors of and are present in the factorisation of = = , it is recommended that and have only very small common factors, if any, besides the necessary 2. Note: The authors of the original RSA paper carry out the key generation by choosing and then computing as the modular multiplicative inverse of modulo , whereas most current implementations of RSA, such as those following PKCS#1, do the reverse (choose and compute ). Since the chosen key can be small, whereas the computed key normally is not, the RSA paper's algorithm optimizes decryption compared to encryption, while the modern algorithm optimizes encryption instead. Key distribution Suppose that Bob wants to send information to Alice. If they decide to use RSA, Bob must know Alice's public key to encrypt the message, and Alice must use her private key to decrypt the message. To enable Bob to send his encrypted messages, Alice transmits her public key to Bob via a reliable, but not necessarily secret, route. Alice's private key is never distributed. Encryption After Bob obtains Alice's public key, he can send a message to Alice. To do it, he first turns (strictly speaking, the un-padded plaintext) into an integer (strictly speaking, the padded plaintext), such that by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext , using Alice's public key , corresponding to This can be done reasonably quickly, even for very large numbers, using modular exponentiation. Bob then transmits to Alice. Note that at least nine values of will yield