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