tính toán modulo nhanh bằng Python và Ruby

Question

tôi đã được trao các thuật toán sau đó tính là nơi s = g^u mod p bằng 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 

Tuy nhiên, khi tôi chuyển đổi mã Ruby như vậy :

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 

Tôi nhận được kết quả khác nhau. Ví dụ:

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 

Đó là câu trả lời đúng từ mã Python so với

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

bất cứ ai có thể giải thích điều này? Từ những gì tôi đã đọc Python và Ruby có cú pháp tương tự cho bithift và bitwise và được sử dụng trong mã, vì vậy tôi không nghĩ rằng đó là. Bất cứ ai có ý tưởng nào khác?

Answer 1

Đó là vì bitwise- & trả về số và 0 là "falsey" bằng Python nhưng "trung thực" trong 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 

Lưu ý rằng s thay đổi giữa dòng thứ hai và thứ ba, mặc dù u là ngay cả ở thời điểm đó. Hãy nhớ rằng 1100 = 12, chúng tôi thấy rằng 12 & 1 == 0. Vì vậy, trong Python, kiểm tra if u & 1: không thành công; nhưng trong Ruby, trong đó 0 được coi là đúng giá trị, if u & 1thành công.

Thử thay thế dòng đó bằng if u & 1 != 0.

Answer 2

0 không phải là giá trị sai trong Ruby. Bạn cần thay đổi if u&1 thành if (u&1) != 0.