Introduction to Cryptography

Veikko Keränen, Jouko Teeriaho (RAMK, 2006)

ELEMENTARY NUMBER THEORY AND ALGORITHMS

2.  Euclidean Algorithm

2.2  Linear Combination with Integer Coefficients  gcd(a, b) = u a + v b

In cryptography, remainders  (r  modulo  b)  are often used in computations with large integers, say  a  and  b  (a = qb + r).  Inverses of large integers  a  (modulo  b)  are central, as we will see later.  By Theorem 1.4 there exists multipliers  u  and  v \(TraditionalForm\`\(\(∈\)\(\ \)\(ℤ\)\)\)  such that gcd(a, b) can be represented in the form  gcd(a, b) = u a + v b.  In the case that  gcd(a, b) = 1,  as we had in Example 2.2, this linear combination has the form  u a + v b = 1.  Here we obtain  u a = (–v) b + 1,  i.e.,  u a  ≡  1 (modulo b)  and thus  u ≡ (a^(-1)) (modulo b).  Consequently, the linear combination 1 = gcd(a, b) = u a + v b  can be directly utilised for finding inverses  (a^(-1)) (modulo b).  The notation  x ≡ y (mod m)  means that  m  divides  the difference of  x  and  y,  i.e.,  x - y = q m,  i.e.,  x = q m + y  for some  q  ∈  ℤ.  In this case we say that the integers  x  and  y  are congruent modulo  m.  Congruenses will be discussed in more detail in Chapter 3.

When we wish to find the multipliers u and v in Theorem 1.4, i.e., we wish to represent  gcd(a, b)  in the form  gcd(a, b) = u a + v b,  the Euclidean algorithm 2.1 can be extended in the way that we discuss next (Algorithm 2.2). Note that leaving off the rows containing symbols  (Subscript[u, i])  and  (Subscript[v, i])  sisältävät, this (extended) algorithm comes back to the basic Euclidean algorithm, where 

 gcd(a, 
          b) = gcd((Subscript[r, -1]), 
            (Subscript[r, 0])) = gcd((Subscript[r, 0]), 
              (Subscript[r, 1])) = gcd((Subscript[r, 1]), 
                (Subscript[r, 2])) = … = gcd((Subscript[r, n - 1]), 
                    (Subscript[r, n])) = gcd((Subscript[r, n - 1]), 0) = 
                    (Subscript[r, n - 1]).

The proof for the Algorithm 2.2 can be found in Appendix 1, where it is discussed in detail how one arrives at this straightforward computational method. In Appendix 1 it is also shown that the remainder  (Subscript[r, i])  produced by the division algorithm can be represented at each step in the form  (Subscript[u, i]) a + (Subscript[v, i]) b.  The last remainder  (Subscript[r, n])  being zero, the last remainder differing from zero, i.e.,  (Subscript[r, n - 1])  is exactly the sought linear combination  d = gcd(a, b) = (Subscript[r, n - 1]) = u a + v b.   In Appendix 1 this algorithm is proved by using mathematical induction and many computations by hand are represented there. Furthermore, from Appendix 1 the reader may find a method  that uses matrix multiplication in computing the linear combination. Finally, Appendix 1 contains a Mathematica program that shows all the intermediate steps. That program can also be transformed into other programming environment forms.

Algorithm 2.2		Extended Euclidean Algorithm 

	input		a ≥ b > 0
	intial values	(Subscript[r, -1]) = a;  (Subscript[r, 0]) = b;
			  (Subscript[u, -1]) = 1; (Subscript[u, 0]) = 0; (Subscript[v, -1])  = 0; (Subscript[v, 0])  = 1;n=0;
	while  (Subscript[r, n]) > 0  do  begin
					  set  	n = n + 1;
				   write	(Subscript[r, n - 2])=(Subscript[q, n])(Subscript[r, n - 1])+(Subscript[r, n]),  (Subscript[r, n - 1]) > (Subscript[r, n]) ≥ 0;
				   set 	(Subscript[u, n])=(Subscript[u, n - 2])-(Subscript[q, n]) (Subscript[u, n - 1]);
				   set 	(Subscript[v, n])=(Subscript[v, n - 2]) - (Subscript[q, n]) (Subscript[v, n - 1]);
				end
	set	 u=(Subscript[u, n - 1]); v= (Subscript[v, n - 1]);

(2.2) 	gcd(a, b) = (Subscript[r, n - 1]) = u a + v b

Proof: 
See Appendix 1.

□

We present one example of a run of the program extendedEuclid written in Appendix 1 (compare this with Example 2.1 before):

extendedEuclid[129,  15]

Let us now compute this linear combination by hand in another way which, at the beginning at least, might look easier to understand.  This method starts from the bottom line and advances to the top line.  In the exam, you may select your way of computing - either straightforwadly from top to bottom (above) or from bottom to top (below).

Example 2.3
Find the greatest comon divisor of  a = 129  and  b = 15, and represent it in the form  u*129 + v*15.
In Example 2.1 we have already seen that the last remainder differing from zero is = 3 = gcd(129, 15).  However, let us still repeat those computations:

({{(row 1)           129, "=", 8, "*", 15, "+", 9}, {(row 2)           15, "=", 1, "*", 9, "+", 6 }, {(row 3)           9, "=", 1, "*", 6, "+", 3}, {(row 4)           6, "=", 2, "*", 3, "+", 0}, {"", "", "", "", "", "", ""}})

We start from row 3 containing the last remainder differing from zero (gcd = 3).  Solving the remainder we obtain:

	3 = 9 - 1*6	(row 3)

Now, from row 2 one can solve the preceeding remainder  6 = 15 - 1*9.   Substituting the expression (15 - 1*9) for the integer  6  above gives:

	3 	=  9 - 1*6 			(row 3)
		=  9 - 1*(15 - 1*9) 		(row 2)
		=  -1*15 + 2*9			(simplification)
	
From row 1 we solve the remainder  9 = 129 - 8*15  (note that a = 129 and b = 15).  Substituting the expression (129 - 8*15)  for the integer  9  in the last simplified expression gives:

	3	=  9 - 1*6 			(row 3)
		=  9 - 1*(15 - 1*9) 		(row 2)
		=  -1*15 + 2*9 		(simplification)
		=  -1*15 + 2*(129 - 8*15)	(row 1)
		=  2*129 + (-17)*15		(simplification)
	   
Therefore, the linear combination in question is  3 = gcd(129, 15) = u a + v b = 2*129 + (-17)*15.

Note that above the term simplification meant that we have collected together (i.e., represented by using one multiplier) the integers that are to be found from rows above, i.e., remainders 3, 6, 9,  or the original integers  b  and  a  (15, 129).  It is important not to compute the products completely, because then we would loose the structure of the expressions. From the point of view of computations these integers are being handled as symbols or strings. The same approach is useful, if one transforms this algorithm to a computer program in a symbolic computational environment.

Example 2.4
Find the greatest comon divisor of  2345  and  123  and represent it in the form  u*2345 + v*123.
In Example 2.2 we have already seen that the last remainder differing from zero is = 1 = gcd(2345, 123).  We repeat the computations here once again:

({{(row 1)            2345, "=", 19, "*", 123, "+", 8}, {(row 2)            123, "=", 15, "*", 8, "+", 3}, {(row 3)            8, "=", 2, "*", 3, "+", 2}, {(row 4)            3, "=", 1, "*", 2, "+", 1}, {(row 5)            2, "=", 2, "*", 1, "+", 0}, {"", "", "", "", "", "", ""}})

The linear combination in question can be computed as follows:

	1	=  3 - 1*2 				(row 4)
		=  3 - 1*(8 - 2*3) 			(row 3)
		=  -1*8 + 3*3 				(simplification)
		=  -1*8 + 3*(123 - 15*8)		(row 2)
		=  3*123 - 46*8			(simplification)
		=  3*123 - 46*(2345 - 19*123)	(row 1)
		=  -46*2345 + (3 + (-46)(-19))*123 	(simplification)
		=  -46*2345 + 877*123 		(simplification)
	   
Therefore, the linear combination in question is  1 = gcd(2345, 123) = u a + v b = (-46)*2345 + 877*123.

In Mathematica this extended Euclidean algorithm is a standard function ExtendedGCD.  The user does not need to pay attention to the order of sizes of the intgers  a  and  b:

a = 963;  b = 4320;  ExtendedGCD[a, b]

Indeed,  9 = gcd(963, 4320) = –157*963 + 35*4320.