Extended Euclidian gCD Algorithm The algorithm Inverse(a, n) is given by -9=nu=1vo=0 -91=au1=0v1=1 - let y=gi-1 div gi 9+1=91-y*g=g1modg1 u#+1=u1-y Vi-1-y when g=0 then inverse(a, n )=VM-1Extended Euclidian GCD Algorithm • The algorithm – Inverse(a,n) is given by: – g0=n u0=1 v0=0 – g1=a u1=0 v1=1 – let • y = gi-1 div gi • gi+1 = gi-1 – y*gi = gi-1 mod gi • ui+1 = ui-1 – y*ui • vi+1 = vi-1 – y*vi – when gi=0 then inverse(a,n) = vi-1