Euclidian algorithm The Euclidian Algorithm is a way of finding the g.c.d. (a, b) without needing to factor a and b Assume a>b First find q and r, such as a=b*+, Then find q2 and r2 such as b=g2*r+r Find qs and rs using r- 2=qr+r for i>2 until r=0 g.c.d. (a,b)=r-I The Euclidian algorithm runs in O(og(a)Euclidian Algorithm • The Euclidian Algorithm is a way of finding the g.c.d.(a,b) without needing to factor a and b. – Assume a>b – First find q1 and r1 such as a=b*q1+r1 – Then find q2 and r2 such as b = q2*r1+r2 – Find q’s and r’s using ri-2=qi*ri-1+ri for i>2 until ri=0. – g.c.d.(a,b)=ri-1 • The Euclidian algorithm runs in O(log3 (a))