# Computing very large exponents

**URL:** <https://www.ruby-forum.com/t/computing-very-large-exponents/60062>\
**Category:** Rails\
**Created:** [May 9, 2006, 10:01pm UTC](https://www.ruby-forum.com/t/computing-very-large-exponents/60062 "2006-05-09T22:01:55Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![doug3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/b3f665/32.png) [@doug3](https://www.ruby-forum.com/u/doug3)\
**Post date:** [May 9, 2006, 10:01pm UTC](https://www.ruby-forum.com/t/computing-very-large-exponents/60062/1 "2006-05-09T22:01:55Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![doug3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/b3f665/32.png) [@doug3](https://www.ruby-forum.com/u/doug3)\
**Post date:** [May 9, 2006, 10:20pm UTC](https://www.ruby-forum.com/t/computing-very-large-exponents/60062/2 "2006-05-09T22:20:30Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![doug3](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/b3f665/32.png) [@doug3](https://www.ruby-forum.com/u/doug3)\
**Post date:** [May 9, 2006, 11:39pm UTC](https://www.ruby-forum.com/t/computing-very-large-exponents/60062/3 "2006-05-09T23:39:05Z")

</div>

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