Modular multiplicative inverse in Ruby
As the comment says on the less-obfuscated version on Rosetta Code, their implementation is based on the Extended Euclidean Algorithm.  Your implementation works by brute force to test every element in the field, so of course it's going to be slow.