, given . On the other hand, if we can find , then we can get (but also and ).
It is now time to give a formal description of the RSA algorithm, as follows.
3.3 The General RSA Algorithm
A (=Alice) wants to send a secret message to B (=Bob). Bob has already chosen two large unequal prime1 numbers and . Bob multiplies and together to get . Bob also chooses some integer bigger than 1. The integer ( for enciphering) must have no factors in common with and no factors in common with . In other words, the greatest common divisor of and is 1 (and similarly for and ). In symbols, we write and . Thus, the only number dividing both and is 1, and the only number dividing both and is 1. We say also that is relatively prime to and to . It follows that .
Because of the conditions imposed on , namely that is relatively prime to , there exists a unique integer ( for deciphering) which is greater than 1 but less than and is such that the remainder of when divided by is 1. It is easy for Bob to calculate , using a method related to the Euclidean Algorithm (see Chapter 19), since Bob knows which are the factors of . There may be other deciphering indices that are easier to work with (see Remark 3.1 part 2 and a more general method in item 3 of the formal algorithm overleaf).
Bob puts the numbers and in a public directory under his name. He keeps secret the primes and : is Bob's private key and the pair is Bob's public key.
Now, Alice has a secret message to transmit to Bob. Alice converts to a number between 1 and represented in binary (which we also denote by ). If is too large, Alice breaks into blocks, each of which is less than . Let us assume, for simplicity, that is less than . Then, Alice enciphers by calculating the cipher text . Note that
