# Exponential calcs with very large exponents

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

## 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=yy%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

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)

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.

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

should 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

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

“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

of +a mod n+,

raised.

# 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

fairly

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

def even?
self[0] == 0
end

primality

probablity

wich gives

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

def prime?(accuracy = 10)
miller_rabin_prime?(accuracy)
end

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

# ‘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

2006/5/10, Sergey V. [email protected]:

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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.