# Exponential calcs with very large exponents

**URL:** <https://www.ruby-forum.com/t/exponential-calcs-with-very-large-exponents/94645>\
**Category:** Ruby\
**Created:** [May 9, 2006, 10:14pm UTC](https://www.ruby-forum.com/t/exponential-calcs-with-very-large-exponents/94645 "2006-05-09T22:14:54Z")\
**Posts on this page:** 5\
**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:14pm UTC](https://www.ruby-forum.com/t/exponential-calcs-with-very-large-exponents/94645/1 "2006-05-09T22:14:54Z")

</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 10, 2006, 2:17am UTC](https://www.ruby-forum.com/t/exponential-calcs-with-very-large-exponents/94645/2 "2006-05-10T02:17:48Z")

</div>

# 

## 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 V.

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

---

<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 10, 2006, 2:59am UTC](https://www.ruby-forum.com/t/exponential-calcs-with-very-large-exponents/94645/3 "2006-05-10T02:59:37Z")

</div>

On Wed, May 10, 2006 at 05:15:06AM +0900, doug meharry wrote:

> for bit j = k - 2 downto 0  
> begin  
> y = y \* y mod n /\* square _/  
> if e(j) == 1 then  
> if e[j] == 1  
> y = y \* x mod n /_ multiply \*/  
> end  
> return y
> 
> Thanks for looking,
> 
> Doug

Integers in ruby has a [] method that returns the bit at the specified  
offset (0 for lsb)

---

<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 10, 2006, 7:36am UTC](https://www.ruby-forum.com/t/exponential-calcs-with-very-large-exponents/94645/4 "2006-05-10T07:36:43Z")

</div>

> > 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.

No, but in case its useful (a long shot), I have some source that does  
it using the “square and multiply” method. Used it to implement RSA in  
pure ruby.

In the hopes it will be useful, here it is.

* * *

# $Id: modn.rb,v 1.3 2004/12/04 20:39:41 sam Exp $

class String

# Convert String to a string of binary digits, similar to

Integer.to\_s(2).  
def to\_bin  
n = self.to\_str

```
s = ''

n.each_byte do |b|
  s << b.to_s(2)
end

s

```

end

# Do I need a Integer#to\_integer and a String.to\_integer? Strings

should be

# allowed as inputs to a lot of the crypto APIs, but they will be

treated as

# integers, internally! How to deal with this?

def to\_integer  
Integer.from\_unsigned\_bytes(self)  
end

def to\_bytes  
self  
end  
end

class Integer

# +bytes+ is a sequence of octets in network byte order (most

significant

# byte first) that comprises an unsigned integer.

def self.from\_unsigned\_bytes(bytes)  
bytes = bytes.to\_str  
n = 0  
bytes.each\_byte do |b|  
n \<\<= 8  
n |= b  
end  
n  
end

# Return self as a String of bytes in network byte order.

def to\_bytes  
a = []  
n = self.to\_int

```
while n != 0
  a.unshift( (n & 0xff).chr )
  n >>= 8
end
a.join

```

end

# Return self.

# 

# Purpose is to allow a set of classes to declare themselves to be

“duck-typed”

# to Integer. This set of classes includes String, see

String#to\_integer.  
def to\_integer  
self  
end

# Why isn’t this a standard ruby method?

def []=(position, value)  
bit = 2 \*\* position  
i = self.to\_int  
if value  
i |= bit  
else  
i &= ~bit  
end  
i  
end

# Determine size of +self+ in bits.

def bit\_size  
i = self.to\_int

```
hibit = i.size * 8 - 1

while( i[hibit] == 0 ) do
  hibit = hibit - 1

  break if hibit < 0
end

hibit + 1

```

end  
end

class Integer

# Calculate the inverse of an Integer modulo +n+. The modular inverse

of +a mod n+,

# +a^-1 mod n+, is a number +a^-1+ such that:

# 

# a^-1 \* a = 1 mod n

# 

# There may not be such a number, in which case a RangeError is

raised.

# 

# Uses the ‘Extended Euclidean Algorithm’ implementation

# from Figure 4.1, +Cryptography Theory and Practice+, Stinson.

def modular\_inverse(n)  
n = n.to\_int  
b = self.to\_int  
n0 = n  
b0 = b  
t0 = 0  
t = 1  
q = (n0/b0).floor  
r = n0 - q \* b0  
while r \> 0 do  
temp = t0 - q \* t  
if temp \> 0 then temp = temp.modulo(n); end  
if temp \< 0 then temp = n - ((-temp).modulo(n)); end  
t0 = t  
t = temp  
n0 = b0  
b0 = r  
q = (n0/b0).floor  
r = n0 - q \* b0  
end

```
if b0 != 1
  raise RangeError, "#{b} has no inverse modulo #{n}"
else
  t.modulo(n)
end

```

end

# Calculate +self+ \*\* +exp+ modulo +n+.

# 

# This method uses the “square and multiply” approach. Why should be

fairly

# obvious from the code, see +Cryptography Theory and Practice+,

Stinson,

# Chapter 4.4 for a description of the method.

def modular\_exp(exp, n)  
# x \*\* b mod n  
x = self.to\_int  
b = exp.to\_int  
n = n.to\_int

```
z = 1

(n.bit_size - 1).downto(0) do |i|
  z = z ** 2 % n

  if b[i] == 1 then
    z = z * x % n
  end
end

z

```

end

# Return whether +self+ is even, that is, evenly divisible by 2.

def even?  
self[0] == 0  
end

# True if +self+ is probably prime, false otherwise. Probabalistic

primality

# test is the Miller-Rabin algorithm, aka “strong pseudo-prime test”.

# 

# +accuracy+ is the number of times to try the test, and error

probablity

# will be aproximately 1 time out of 4\*\*+accuracy+. Default is 10,

wich gives

# an error rate of 1 in 1,048,076.

def prime?(accuracy = 10)  
miller\_rabin\_prime?(accuracy)  
end

# Determines if an odd number is prime, with an error probability of

1/4, at

# most. Implementation from Stinson, Figure 4.9.

def miller\_rabin\_prime?(accuracy)  
# Two is prime  
return true if self == 2  
# Not prime if its even!  
return false if self.even?

```
n = self.to_int

# Find k, m such that n - 1 = (2 ** k) * m, where m is odd

m = n - 1
k = 0

# Since n is odd, n-1 is even, and this will loop at least once
while m.even?
  m >>= 1
  k += 1
end

# Answers of 'composite' are always correct - n is not prime. 

```

Answers of  
# ‘prime’ are not necessarily true, so we try again. If we answered  
‘prime’  
# accuracy number of times, then maybe it is prime.  
accuracy.times do

```
  catch(:isprime) do
    # Choose a, 1 <= a <= n - 1
    a = Kernel.rand(n - 1) # 0..(n-2)
    a = a + 1 # 1..n-1

    # Compute b = a ** m mod n
    b = a.modular_exp(m, n)

```

# puts “n #{n} m #{m} k #{k} a #{a} b #{b}”

```
    # If b == 1 mod n, n is prime
    if( b == 1 )
      throw :isprime
    end

    # For i = 0 to k - 1 do
    k.times do
      # if b == -1 (mod n), n is prime
      if( b == (n - 1) )
        throw :isprime
      else
        b = b.modular_exp(2, n)
      end
    end

    # It's composite.
    return false
  end

end

return true

```

end

end

---

<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 10, 2006, 9:02am UTC](https://www.ruby-forum.com/t/exponential-calcs-with-very-large-exponents/94645/5 "2006-05-10T09:02:23Z")

</div>

2006/5/10, Sergey V. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

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

Dunno whether any of these is faster

> > require ‘mathn’  
> > =\> true  
> > x=1\<\<40  
> > =\> 1099511627776  
> > k=(“%b” % x).length - 1  
> > =\> 40  
> > x[k]  
> > =\> 1  
> > k=Math.log(x)/Math.log(2)  
> > =\> 40.0  
> > x[k]  
> > =\> 1

Kind regards

robert