Euclidean algorithm (EA)
This algorithm computes gcd or greatest common divider. This is very important in PKC (public key cryptography). So if somebody gives you two integers r0,r1, find gcd(r0,r1), i. e. the largest integer that divides both numbers.
Example r0=27, r1=21. How to solve this? lets do prime factorization
27 = 3x3x3 21 = 3x7 What is same? the number 3. so 3=gcd(27,21)
It has a one big issue. It doesnt work good with large numbers. It doesnt work in practice, because in practice cryptography we are using numbers so big that we cannot factorize them. So is there faster method available? Yes there is. Its the euclidean algorithm. In general EA is reduction algorithm. It tries to reduce the size of numbers to two smaller numbers and then reduce the numbers again till we can see gcd. Below is the algorithm, proof is in the book.
gcd(r0,r1) = gcd(r0 mod r1,r1); we assume that r0 > r1, and that both numbers are positive integers also gcd(r0,r1) = gcd(r1, r0 mod r1) Example r0=27, r1=21 gcd(27,21) = gcd(27 mod 21,21) = gcd(6,21) gcd(21,6) = gcd(21mod6,6) = gcd(3,6) Note that we can swap the numbers in bracketslike we did with gcd(6,21) because we search for theirs common divider, so it doesnt matter what is first number but we need to have r0>r1 so we can compute the mod. gcd(6,3) = 3 Note when remainder is 0 we are done ;-)
Example: Given gcd(973, 301) do the calculation
973(r0) = 3(q1) x 301(r1) + 70(r2) 301(r1) = 4(q2) x 70(r2) + 21(r3) 70(r2) = 3(q3) x 21(r3) + 7(r4) 21(r3) = 3(q4) x 7(r4) + 0 gcd(973,301) = 7
Extended Euclindean algorithm
Again given two integers r0, r1, find gcd(r0,r1). But now in addition we would like to compute s and t for gcd(r0,r1) = s x r0 + t x r1. The s and t are very useful.
The idea is to firstly compute regular EA algorithm and then do the form above with s and t numbers. And thats it. But how do the form with s and t? Lets see the previous example but with EEA applied
gcd(973,301) = s x 973 + t x 301 = 7 EA step 1 973(r0) = 3(q1) x 301(r1) + 70(r2); EEA form r2 = s x r0 + t x r1; 70 = 1 x 973 + (-3) x 301 ----------------------------------------------------------------------------------------------------------- EA step 2 301(r1) = 4(q2) x 70(r2) + 21(r3); EEA form r3 = s x r0 + t x r1; 21 = 1 x 301 - 4 x 70 = 301 - 4 x (973 - 3 x 301); 21 = -4 x 973 + 13 x 301 ----------------------------------------------------------------------------------------------------------- EA step 3 70(r2) = 3(q3) x 21(r3) + 7(r4); EEA r4 = s x r0 + t x r1; r4 = 70 - 3 x 21 = (973 - 3 x 301) - 3 x (-4 x 973 + 13 x 301); 7 = 13 x 973 + (-42) x 301 ----------------------------------------------------------------------------------------------------------- step 4 21(r3) = 3(q4) x 7(r4) + 0; we know that the 7 is the gcd! So why is cool that other patter? We can write that 7 also like this: 7 = gcd(r0,r1) = r4 = 13 x 973 + (-42) x 301
In step 2 we expressed that 70 with equation one line above and then we altered the formula to original r0, r1 image. Why? Because we want to have it in form gcd(r0,r1) = s x r0 + t x r1 or gcd(973,301) = s x 973 + t x 301. We gonna do that on every step to have the origin form. We will just substitute the numbers.
But the milion dolar question is why we gave a fuck and did all this pain computations? Main application of the EEA is to compute INVERSE of MOD n. Lets take a look more on it:
a on -1 x a = 1 mod n
gcd(n,a) = 1 = s x n + t x a = 1 /mod n (s x n / mod n = 0)
t x a = 1 (that means that t is a on -1 !!!)
The parameter t of the EEA is the inversion of r1 mod r0!!!!
Eulers Phi function
Zm = {0,1,......., m-1} .... And you would like to know how many of these numbers are relativly prime to m.
For reason you will understand later. Numbers are relatively prime if they their gcd = 1.
gcd (0,m) = m
gcd (1,m) = ?
gcd (2,m) = ?
...
And you are just interested how many of these integers are relatively prime. You are not interested about what specific number but just how many.