Extended Euclidian gCD Algorithm In some cryptographic algorithm you want to find a inverse a-I such as a*a-l=1 mod n We use the fact that if d-g.cd(a, b ) where a>b, then there exists integer u and v such that d=u*a+v*b finding u and v can be done in o(oga) Then we use an extended euclidian algorithm to find a, assuming g.c.d. (a, n)=1Extended Euclidian GCD Algorithm • In some cryptographic algorithm you want to find a inverse a-1 such as a*a-1=1 mod n • We use the fact that – if d = g.c.d.(a,b), where a>b, then there exists integer u and v such that d = u*a + v*b. – finding u and v can be done in O(log3a) • Then we use an extended Euclidian algorithm to find a-1 , assuming g.c.d.(a, n) = 1