Extended Euclidean algorithm

Can be used to determine if a number g belongs in a multiplicative group Zp* since it finds the integers x,y such that:

gx+py = gcd(g,p)

where x is the multiplicative inverse of a mod b. If 1 < x < p-1 then the number g belongs Zp*.

Cheers,
Steve