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

on 2006-05-10 00:01

on 2006-05-10 00:20

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

on 2006-05-10 01:39

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