A function for finding the modular multiplicative inverse, based on an extended version of the Euclidean algorithm.

def EGCD(b,m,recLevel=0)
  if b % m == 0
          tmpVal = [0,1]
          return tmpVal
  else
          tmpVal = EGCD(m, b % m, recLevel+1)
          tmpVal2 = [tmpVal[1], tmpVal[0]-tmpVal[1] * ((b/m).to_i)]
          if recLevel == 0
                return tmpVal2[0] % m
          else
                return tmpVal2
          end
  end
end