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=gcd (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 odog a 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