モジュラ累乗の右から左への2進法の時間複雑さを証明する必要があります

Question

Right-to-Left Method私はモジュラ累乗のアルゴリズムを実装するために使用しましたが、私の教授は時間の複雑さはO（ログ指数）ウィキペディアは信頼できるソースではありません。

とにかく、擬似コードの取得元を確認しましたが、時間の複雑さは示されていません。これに対して有効な学術資料を誰かが見つけられるよう助けることができますか？

Answer 1

安全に派生できるものには、学術的な情報源は必要ありません。

あなたは右から左への方法を使用してべき乗剰余演算を実行するとき、あなたは2つのn桁の数字、bとm、およびkビット指数eで始まります。

modular_pow(b, m, e) 
    if m = 1 { 
     return 0 
    } 
    res = 1 
    b = b mod m 
    while e != 0 
     if e mod 2 == 1 { 
      res := (res * b) mod m 
     } 
     e >>= 1 
     b = (b * b) mod m 
    return res 

ループが停止する前に、2によってループの各ステップは、1回のまたは2つの乗算を行い、1つまたは2つのログ E分割を実行することに等価である、指数eのkビットシフトを行いますmod操作です。これはO（k * M（n））の全体的な時間複雑さにつながります。ここで、M（n）は乗算アルゴリズムの時間複雑度です。

教授は、その時の複雑さは、特定の条件の下でO（ログ指数）

時間の複雑さは、可能性がO（指数を記録）することができないと言う - M（N）の時間複雑性はありますO（1）。これは、最新のCPUのプリミティブ番号に当てはまります。

ほとんどの場合、あなたの教授はより興味深いケース話していた - すなわち、bとmがnが実用的な上限はありませんn桁の数字、あるとき。

This pageは、乗算アルゴリズムに応じてM（n）の可能な時間複雑度を列挙する。 Fürerのアルゴリズムでは、教科書の長時間乗算のO（n ）からO（n * log n * 2 ^{O（log * n）}）までの複雑さがあります。