Euclidean Algorithm (1 Viewer)

[MouNtY]

ok so i was takin a squiz at Cryptanalysis on Wikipedia and i ran into the Euclidiean Algorithm (http://en.wikipedia.org/wiki/Euclidean_algorithm), used on i think it was RSA.

I was looking at how it was done, and maybe it's just cause i'm stupid but i couldn't figure it out even though it looked really simple.

So would somebody be able to help a guy out, an just explain how it's supposed to work


Any help would be much appreciated.


PS - i have a feeling i've done it before, i don't know why, it just looks familiar

 

[martin]

Yeah, that isn't the most useful description of the euclidean algorithm is it? It's used to find the gcd (greatest common divisor) of two integers. So say we want to find gcd(72,52). We could just factor them 72=(2^3)*(3^2) and 52=(2^2)*13 so gcd(72,52)=2^2=4.

But factoring is hard (for big numbers) so use Euclidean algorithm instead

72=1*52+20
52=2*20+12
20=1*12+8
12=1*8+4
8=2*4+0

Hopefully you can see the pattern here. The gcd is given by the last nonzero remainder (4 as we expected).

The Extended Euclidean algorithm allows us to find integer solutions to the equation ax+by=d where d is a multiple of gcd(a,b).

so say we want to solve 72x+52y=4 for x,y integers, working backwards from working above

4
=12-1*8
=12-1*(20-12)
=2*12-20
=2*(52-2*20)-20
=2*52-5*20
=2*52-5*(72-52)
=7*52-5*72

so x=-5, y=7 is a soln (there are others).

This can be used to find multiplicative inverses in Zp which are required in RSA.

 

[MouNtY]

OMG!, mate you're the best

i get it now, thanks heaps for your help.

 

[Slidey]

The Euclidean algorithm was removed from the equivalent 4unit course when the HSC was introduced, along with matrices and other interesting things. Humbug.