ruby - Rubyの大きな指数?

Question

私はちょうど大学関連の Diffie Hellmann の演習を行っており、そのために ruby を使用しようとしました。悲しいことに、Ruby は大きな指数を処理できないようです。

警告: a**b では、b が大きすぎる可能性があります
NaN
[...]

それを回避する方法はありますか？(例えば、特別な数学のクラスか、それに沿った何か?)

ps問題のコードは次のとおりです。

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

score 10 · Accepted Answer

10

いわゆるべき乗剰余を実行する必要があります。

于 2009-11-18T20:09:55.193 に答える

score 3 · Accepted Answer

OpenSSL バインディングを使用できる場合は、Ruby で急速な剰余累乗を実行できます。

puts some_large_int.to_bn.mod_exp(exp,mod)

score 2 · Accepted Answer

これらの巨大な数を取得せずに a^b mod n を計算する良い方法があります。

各段階でモジュラスを取りながら、自分でべき乗を見ていきます。一連の 2 の累乗に分解できるトリックがあります。

これを使用して RSA を実行する例のリンクを次に示します。これは、少し前に受講したコースからのものです。具体的には、2 ページ目に例を示します。 /RSAExample.pdf

ウィキペディアのサンプル疑似コードを使用した詳細な説明: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

score 1 · Accepted Answer

ルビーはわかりませんが、bignumに適した数学ライブラリでさえ、そのような式を素朴な方法で評価するのに苦労します（7789の415492の累乗は約160万桁です）。

a^b mod p爆破せずに解決する方法は、すべてのべき乗でmod pingを実行することです-言語はそれ自体でこれを解決していないので、助けなければならないと思います。

score 1 · Accepted Answer

私は自分でいくつかの試みをしました。2 乗による累乗はこれまでのところうまく機能しますが、bigNum でも同じ問題が発生します。のような再帰的なもの

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

しかし、私が気付いているように、実質的なものを ruby のプライムクラスに依存するのはひどい考えです。Ruby は素数生成にエラトステネスのふるいを使用していますが、さらに悪いことに、gcd などに試行分割を使用しています....

ああ、@@mod はクラス変数だったので、これを自分で使用する予定がある場合は、param などとして追加することをお勧めします。私はそれが非常に迅速に機能するようになりました

puts a.exponentiation(100000000000000, 1222555345678)

その範囲の数字。

(@@mod = 80233 を使用)

score 1 · Accepted Answer

OK、二乗法が機能するようになりました

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

出力: 59357797

暗号コースで発生する可能性のある問題にはこれで十分だと思います

score 0 · Accepted Answer

これは、Wikipediaの右から左へのバイナリメソッドの例に触発されています。

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

ruby - Rubyの大きな指数?

8 に答える 8

Related

Reference