Große Exponenten in Ruby?

Question

Ich mache gerade ein paar Diffie Hellmann Übungen und versuchte Ruby dafür zu benutzen. Leider Rubin scheint nicht mit großen Exponenten umgehen zu können:

Warnung: im ** b kann b
[...]

zu groß
NaN

Gibt es einen Weg um es herum? (z.B. eine spezielle Mathematikklasse oder etwas entlang dieser Linie?)

p.s. hier ist der Code in Frage:

generator = 7789 
prime = 1017473 
alice_secret = 415492 
bob_secret = 725193 

puts from_alice_to_bob = (generator**alice_secret) % prime 
puts from_bob_to_alice = (generator**bob_secret) % prime 

puts bobs_key_calculation = (from_alice_to_bob**bob_secret) % prime 
puts alices_key_calculation = (from_bob_to_alice**alice_secret) % prime 

Answer 1

Sie müssen tun, was genannt wird, modular exponentiation.

Answer 2

Ich kenne Ruby nicht, aber selbst eine Bignum-freundliche Mathebibliothek wird Mühe haben, einen solchen Ausdruck naiv auszuwerten (7789 zur Potenz 415492 hat etwa 1,6 Millionen Ziffern).

Die Art und Weise a^b mod p zu arbeiten, ohne Sprengung ist die mod p ing bei jeder Potenzierung zu tun - Ich würde vermuten, dass die Sprache, dies allein nicht funktioniert und deshalb muss geholfen werden.

Answer 3

Es gibt eine gute Möglichkeit, ein^b mod n zu berechnen, ohne diese riesigen Zahlen zu erhalten.

Sie werden selbst durch die Exponentiation gehen, indem Sie in jeder Phase den Modulus nehmen. Es gibt einen Trick, wo Sie es in eine Reihe von Zweierpotenzen zerlegen können.

Hier ist ein Link mit einem Beispiel unter Verwendung es RSA zu tun, von einem Kurs ich vor einer Weile nahm: Insbesondere auf der zweiten Seite können Sie sehen, ein Beispiel: http://www.math.uwaterloo.ca/~cd2rober/Math135/RSAExample.pdf

Weitere Erklärung mit einigen Probe Pseudocode aus Wikipedia: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

Answer 4

Ich habe einige eigene Versuche gemacht. Die Potenzierung durch Quadrieren funktioniert bisher gut, aber das gleiche Problem mit bigNum. eine solche rekursive Sache wie

def exponentiation(base, exp, y = 1) 
    if(exp == 0) 
     return y 
    end 
    case exp%2 
     when 0 then 
      exp = exp/2 
      base = (base*base)%@@mod 
      exponentiation(base, exp, y) 
     when 1 then 
      y = (base*y)%@@mod 
      exp = exp - 1 
      exponentiation(base, exp, y) 
    end 
end 

wäre es jedoch sein, wie ich zu realisieren, eine schreckliche Idee für erhebliche alles auf Rubys prime Klasse zu verlassen. Ruby verwendet das Sieb von Eratosthenes für seinen prime generator, aber noch schlimmer, es verwendet Trial division für gcd's und so ....

oh, und @@ mod war eine klassenvariable, also wenn du diese selbst verwenden willst Vielleicht möchten Sie es als Parameter oder etwas hinzufügen. Ich habe es bekommen ziemlich schnell zu arbeiten für

setzt a.exponentiation (100000000000000, 1222555345678)

Zahlen in diesem Bereich.

(mit @@ mod = 80233)

Answer 5

OK, bekam die Quadratur-Methode für die Arbeit

a = Mod.new(80233788) 
puts a.exponentiation(298989898980988987789898789098767978698745859720452521, 12225553456987474747474744778) 

Ausgabe: 59357797

Ich denke, dass Sie vielleicht für jedes Problem ausreichend sein sollte, haben Sie in Ihrem Crypto-Kurs

Answer 6

Wenn Sie die OpenSSL-Bindungen verwenden können, dann können Sie schnelle modulare Exponentiation in Ruby

tun

puts some_large_int.to_bn.mod_exp(exp,mod) 

Answer 7

Wenn Sie wirklich zu BIG modularen Exponentiation gehen wollen, hier ist eine Implementierung von der Wiki-Seite.

#base expantion number to selected base 
def baseExpantion(number, base) 
    q = number 
    k = "" 
    while q > 0 do 
    a = q % base 
    q = q/base 
    k = a.to_s() + k 
    end 
    return k 
end 

#iterative for modular exponentiation 
def modular(n, b, m) 
    x = 1 
    power = baseExpantion(b, 2) #base two 
    i = power.size - 1 
    if power.split("")[i] == "1" 
     x = x * n 
     x = x % m 
    end 
    while i > 0 do 
     n *= n 
     n = n % m 
     if power.split("")[i-1] == "1" 
     x *= n 
     x = x % m 
     end 
     i -= 1 
    end 
    return x 
end 

Ergebnisse, wo

mit Wolfram Alpha getestet

Answer 8

Dieser von right-to-left binary method Beispiel auf Wikipedia inspiriert:

def powmod(base, exponent, modulus) 
    return modulus==1 ? 0 : begin 
    result = 1 
    base = base % modulus 
    while exponent > 0 
     result = result*base%modulus if exponent%2 == 1 
     exponent = exponent >> 1 
     base = base*base%modulus 
    end 
    result 
    end 
end