From: Sergey Volkov <gm.vlkv@...>
Date: 2006-05-10T09:17:56+09:00
Subject: Re: Exponential calcs with very large exponents

#
## Use Fixnum#[] - Bit Reference
#
def modexp x, e, n
    return 1%n if e.zero?
    # k - most significant bit posistion
    ee, k = e, 0
    # linear search
    (ee>>=1;k+=1) while ee>0
    y = x
    (k-2).downto(0) do |j|
        y=y*y%n  # square
        (y=y*x%n) if e[j] == 1 # multiply
    end
    y
end
__END__

Btw: do you know how to find most significant bit faster?
Sergey Volkov

doug meharry wrote:
> 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/.