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
--
Posted via http://www.ruby-forum.com/.
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 On May 9, 2006, at 04:01 PM, doug meharry wrote:> 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
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. > > -BrianThanks Brian, I realized that shortly after posting and went ahead and reposted on the other list. Doug -- Posted via http://www.ruby-forum.com/.