cálculos de módulo rápidos en Python y Ruby

Question

que me han dado el siguiente algoritmo que calcula es donde s = g^u mod p en 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 

Sin embargo, al convertir el código a Ruby como tal :

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 

Tengo salida diferente. Por ejemplo:

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 

que es la respuesta correcta a partir del código Python en comparación con

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

¿Alguien puede explicar esto? Por lo que he leído Python y Ruby tienen la misma sintaxis para bitshift y bitwise y se usan en el código, así que no creo que sea eso. ¿Alguien tiene alguna otra idea?

Answer 1

Es porque bitwise- & devuelve un número y 0 es "Falsey-" en Python, pero "Truthy" en 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 

Tenga en cuenta que s cambios entre la segunda y la tercera línea, a pesar de u es aún en ese punto. Recordando que 1100 = 12, vemos que 12 & 1 == 0. Entonces, en Python, la prueba if u & 1: falla; pero en Ruby, donde 0 se considera valor verdadero, if u & 1tiene éxito.

Intente reemplazar esa línea con if u & 1 != 0.

Answer 2

0 no es un valor falso en Ruby. Necesita cambiar if u&1 a if (u&1) != 0.