Exponential calcs with very large exponents


#1

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


#2

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


#3

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)


#4

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


#5

2006/5/10, Sergey V. 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