Euclidian Algorithm g.c.d(a, b) without needing to factor a and 6e The euclidian algorithm is a way of finding the ng assume a>b First find q and r such as a=b*q+r Then find q2 and r 2 such as b=g2* r+r2 Find qs and rs using r- 2=q r +r for i2 until; =0 g.c.d. (a,b= 1-1 The Euclidian algorithm runs in O(log(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))