 # Computing very large exponents

Greetings all.

Does anyone have a clue how to use Ruby to do modular exponentiation
using the binary left-to-right method? I looked through the
documentation and searched the forums and found the String.each_byte
method. However I had no luck finding anything showing how one might
manipulate bits of bytes.

Below is an example of what I am talking about.

The calculation a = b^e mod n (or in Ruby: a = (b ** e).modulo(n) )is
known as modular exponentiation. One efficient method to carry this out
on a computer is the binary left-to-right method. To solve y = x^e mod n
let e be represented in base 2 as

e = e(k-1)e(k-2)…e(1)e(0)

where e(k-1) is the most significant non-zero bit and bit e(0) the
least.
set y = x
for bit j = k - 2 downto 0
begin
y = y * y mod n /* square /
if e(j) == 1 then
y = y * x mod n /
multiply */
end
return y

Thanks for looking,

Doug

FYI… this is why there’s a Ruby T. mailing list. While this is
interesting, it has nothing to do with Rails, so really shouldn’t be
on this list.

-Brian

Brian H. wrote:

FYI… this is why there’s a Ruby T. mailing list. While this is
interesting, it has nothing to do with Rails, so really shouldn’t be
on this list.

-Brian

Thanks Brian,

I realized that shortly after posting and went ahead and reposted on the
other list.

Doug

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.