Python和Ruby中的快速取模计算

Question

我得到了一个算法，它用来计算 s，其中 s = g^u mod p，代码是用 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

但是，当我把这段代码转换成 Ruby 时，像这样：

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

我得到的结果却不一样。例如：

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

这是 Python 代码的正确答案，而与之相比：

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

有没有人能解释一下这个问题？我看到 Python 和 Ruby 在代码中使用的位移和按位与的语法是一样的，所以我觉得问题不在这里。有没有其他人有想法？

Answer 1

在Ruby语言中，0并不是一个假值。你需要把 if u&1 改成 if (u&1) != 0。

Answer 2

这是因为位运算符&返回的是一个数字，在Python中，0被认为是“假”的，但在Ruby中，0却被认为是“真”的。

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

注意到在第二行和第三行之间，s的值发生了变化，尽管此时u是偶数。记住1100 = 12，我们可以看到12 & 1 == 0。所以在Python中，测试if u & 1:会失败；但在Ruby中，0被视为真值，if u & 1 成功。

你可以尝试把那行代码换成if u & 1 != 0。