![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
4.2 More Number TheoryBefore describing how RSA works, we need to discuss some more facts concerning modular arithmetic and number theory. Two fundamental results that we require are the Euclidean algorithm and the Chinese remainder theorem. 4.2.1 The Euclidean AlgorithmWe already observed in Chapter 1 that The set of residues modulo n that are relatively prime to n is denoted At this point, we know that any First, we describe the Euclidean algorithm, in its basic form, which is used to compute the greatest common divisor of two positive integers, say r0 and r1, where r0 > r1. The Euclidean algorithm consists of performing the following sequence of divisions: Then it is not hard to show that Hence, it follows that gcd(r0, r1) = rm. Since the Euclidean algorithm computes greatest common divisors, it can be used to determine if a positive integer b < n has a multiplicative inverse modulo n, by starting with r0 = n and r1 = b. However, it does not compute the value of the multiplicative inverse (if it exists). Now, suppose we define a sequence of numbers t0, t1, . . ., tm according to the following recurrence (where the qjs are defined as above): Then we have the following useful result. THEOREM 4.1 For 0 ≤ j ≤ m, we have that rj ≡ tjr1 (mod r0), where the qjs and rjs are defined as in the Euclidean algorithm, and the tjs are defined in the above recurrence. PROOF The proof is by induction on j. The assertion is trivially true for j = 0 and j = 1. Assume the assertion is true for j = i - 1 and i - 2, where i ≥ 2; we will prove the assertion is true for j = i. By induction, we have that and Now, we compute: Hence, the result is true by induction. The next corollary is an immediate consequence. COROLLARY 4.2 Suppose gcd(r0, r1) = 1. Then tm = r1-1 mod r0. Now, the sequence of numbers t0 , t1, . . . tm can be calculated in the Euclidean algorithm at the same time as the qjs and the rjs. In Figure 4.1, we present the extended Euclidean algorithm to compute the inverse of b modulo n, if it exists. In this version of the algorithm, we do not use an array to keep track of the qjs, rjs and tjs, since it suffices to remember only the last two terms in each of these sequences at any point in the algorithm. In step 10 of the algorithm, we have written the expression for temp in such a way that the reduction modulo n is done with a positive argument. (We mentioned earlier that modular reductions of negative numbers yield negative results in many computer languages; of course, we want to end up with a positive result here.) We also mention that at step 12, it is always the case that tb ≡ r (mod n) (this is the result proved in Theorem 4.1). Here is a small example to illustrate: Example 4.1 Suppose we wish to compute 28-1 mod 75. The Extended Euclidean algorithm proceeds as follows: Hence, 28-1 mod 75 = 67.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |