Fast modulo calculations in Python and Ruby

Question

I've been given the following algorithm that computes s where s = g^u mod p in Python:

def modexp ( g, u, p ):
   """computes s = (g ^ u) mod p
      args are base, exponent, modulus
      (see Bruce Schneier's book, _Applied Cryptography_ p. 244)"""
   s = 1
   while u != 0:
      if u & 1:
         s = (s * g)%p
      u >>= 1
      g = (g * g)%p;
   return s

However, when I convert the code to Ruby like so:

def modexp ( g, u, p )
    s = 1
    while u != 0
        if u & 1
            s = (s * g)%p
        end
        u >>= 1
        g = (g * g)%p
    end
    return s
end

I get different output. For example:

Python 2.7 (r27:82500, Oct  6 2010, 12:29:13) 
[GCC 4.5.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import modexp
>>> modexp.modexp(96,25,17)
6

Which is the right answer from the Python code compared with

>> require './modexp.rb'
=> true
>> modexp(96,25,17)
=> 14

Can anyone explain this? From what I've read Python and Ruby have the same syntax for the bitshift and bitwise and used in the code, so I don't think it's that. Anyone have any other ideas?

Answer 1

It's because bitwise-& returns a number, and 0 is "falsey" in Python but "truthy" in Ruby.

def modexp ( g, u, p )
    s = 1
    while u != 0
        puts "g: #{g}, s: #{s}, u: #{u.to_s(2)}"
        if u & 1
            s = (s * g)%p
        end
        u >>= 1
        g = (g * g)%p
    end
    return s
end

irb(main):032:0> modexp(96,25,17)
g: 96, s: 1, u: 11001
g: 2, s: 11, u: 1100
g: 4, s: 5, u: 110
g: 16, s: 3, u: 11
g: 1, s: 14, u: 1
=> 14

Note that s changes between the second line and the third, even though u is even at that point. Remembering that 1100 = 12, we see that 12 & 1 == 0. So, in Python, the test if u & 1: fails; but in Ruby, where 0 is considered a true value, if u & 1 succeeds.

Try replacing that line with if u & 1 != 0.

Answer 2

0 is not a false value in Ruby. You need to change if u&1 to if (u&1) != 0.