Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Ruby script to compute modular-exponentiation recursively.
#!/usr/local/bin/ruby
#*************************************
# Modular Exponentiation (recursive).
#*************************************
class ModularExponentiation
def comp_mod_exp(b, e, m)
return 1 if e == 0
ans = comp_mod_exp(b, e / 2, m)
ans = (ans * ans) % m
ans = (ans * b) % m if e % 2 == 1
return ans
rescue => e
raise
end
end
exit unless __FILE__ == $0
begin
# me = b^e mod m
b, e, m = 12345, 6789, 4567
obj = ModularExponentiation.new
me = obj.comp_mod_exp(b, e, m)
puts "#{b}^#{e} mod #{m} = #{me}"
rescue => e
puts "[#{e.class}] #{e.message}"
e.backtrace.each{ |bt| puts "\t#{bt}" }
exit 1
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment