Forum: Ruby on Rails Computing very large exponents

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
E700f28e33f22aa356f21833cfd7cba4?d=identicon&s=25 Doug Meharry (doug3)
on 2006-05-09 22:01
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
7c4087d053eb02d099a17d91ba5e33b5?d=identicon&s=25 Brian Hughes (Guest)
on 2006-05-09 22:20
(Received via mailing list)
FYI... this is why there's a Ruby Talk mailing list. While this is
interesting, it has nothing to do with Rails, so really shouldn't be
on this list.

-Brian
E700f28e33f22aa356f21833cfd7cba4?d=identicon&s=25 Doug Meharry (doug3)
on 2006-05-09 23:39
Brian Hughes wrote:
> FYI... this is why there's a Ruby Talk 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 topic is locked and can not be replied to.