alt="upper M equals Rem left-bracket upper C Superscript d Baseline comma upper N right-bracket equals Rem left-bracket 256 77 9 Superscript 461 047 Baseline comma 808 631 right-bracket equals 205 632"/> 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 are known, it is easy to find the message from by calculating : this is what Bob does. Mathematically, nobody has been able to prove that the factoring problem cannot be solved in a reasonable amount of time. Similarly, it has not been shown that cannot be obtained from in a reasonable amount of time by some method or another. We point out also that given we can find , even when is chosen so that , where divides and divides . (See Buchmann [Buc04]). Thus, the problem of findingis equivalent to the factoring problem.
Let us return again to our example of symmetric key encryption where the enciphering algorithm was “add 7.” In order to avoid overflow and storage, we fix a large positive integer . Let the message be some number between 0 and , i.e.
alt="upper M equals Rem left-bracket upper C Superscript d Baseline comma upper N right-bracket equals Rem left-bracket 256 77 9 Superscript 461 047 Baseline comma 808 631 right-bracket equals 205 632"/> directly using the repeated squaring technique, or take a more efficient approach, as follows: Bob calculates 