WolframAlphaは数字をすばやく指数化できますか？

Question

私は、RSAアルゴリズムがそのような大きな数字をどのように扱うのか、そしてtried one example in WolframAlphaと思っていました。どのように彼らはそのような狂った数に対処することができますか？

編集：ただ、それはより多くの奇妙な作るために、one more example

Answer 1

非常に効率的に^B MOD Cを計算するために使用することができますexponentiation by squaringと呼ばれる単純なアルゴリズムがあります。これは

^2K MOD C =（^K） MOD C

^{2K + 1} MOD C = A＆middotという観察に基づいています。 （^K）のmod C

これを考えると、あなたはこの再帰的なアプローチで^B MOD Cを計算することができます。

function raiseModPower(a, b, c): 
    if b == 0 return 1 
    let d = raiseModPower(a, floor(b/2), c) 
    if b mod 2 = 1: 
     return d * d * a mod c 
    else 
     return d * d mod c 

これはO（Bをログ）の乗算を行いますそれぞれがO（log c）よりも多くの桁を持つことができないので、本当に高速です。これは、RSAの実装がどのように物事を力に上げるかです。再帰的プレゼンテーションは本当にきれいだと思いますが、これを反復的に書き直すことができます。

このアルゴリズムを使用すると、任意の精度の数値を乗算して計算する標準的な手法を使用できます。乗算のO（log b）回の反復しか必要とされないので（b反復とは対照的に）、それは速く狂っている。あなたは実際に^bを計算することは決してありませんし、それはまた、数字の数を低く保ち、それをさらに速くするcでそれを改造します。

希望すると便利です。