alt="d"/>. Thus, the private key is sometimes defined as the triple.
Another example of the RSA algorithm
In the example below, we also briefly indicate how more sophisticated number theory can shorten the calculations.
Suppose Bob chooses the primes and . So , and . A valid choice for is 7, as . Using the Euclidean Algorithm, Bob can also calculate (see Chapter 19). Bob announces his public key and finds . Bob keeps secret. When Alice wants to send to Bob, she computes using the repeated squaring method to find that . Alice then transmits in public, and when Bob receives it, he can either compute directly using the repeated squaring technique, or take a more efficient approach, as follows: Bob calculates and , then uses the Chinese Remainder Theorem (of Chapter 19) to combine them to find . Since , Bob knows that , and by a theorem due to Fermat2 this is equal to . Similarly, . Bob then combines and to find .
Remark 3.4
Note in the above thatis divisible by.
In general, suppose are not divisible by , and assume that is divisible by . Then . Therefore, upon multiplying both sides by .
Remark 3.5
Instead of using 461047 as the deciphering index, Bob can calculate that the least common multiple ofandis. Then he can find that the remainder ofwhen divided byis 1, where, and use this for a deciphering index instead.
It is conceivable that the RSA problem of obtaining from is easier than the factoring problem. For some methods of obtaining from that work in special cases, we refer to the problems. The factoring problem is to obtaingiven. Once
