2

クラスでは、2^n mod(m) のアルゴリズムが提示されました。

    to find 2^n mod(m){  
      if n=0 {return 1;}  

      r=2^(n-1)mod(m);  
      if 2r < m {return 2r;}  
      if 2r > =m {return 2r-m;}  
    }

実行時間は O(n*size(m)) で、m のサイズは m のビット数であると言われました。

n の部分はわかりますが、サイズ (m) については引き算が関係しないと説明できません。誰かがそれに光を当てることができますか？

前もって感謝します。

4

2 に答える 2

0

これは暗号化で使用されていると思います（いわゆる不可逆関数）。

再帰的に計算する必要がある場合(2**n) mod m、これが最も明白な方法です。再帰の深さはnであるため、O(n)複雑さは明らかです。

ただし、任意のサイズ (暗号化では 512 ビットのキーが可能であり、どの算術レジスタよりもはるかに大きい) をサポートしたい場合はm、それも考慮する必要があります (ほとんどの場合、任意精度の算術を使用する必要はありません。したがって、この用語は通常 1) です。

EDIT @Mysticial: 関数はハードウェアmod操作を明示的に呼び出しません。それが行うのは、シフトと減算だけです。O(1)加算/減算が行われている間、シフトは常に行われますO(ceil(m/sizeof_ALU_precision))

于 2011-10-13T00:34:22.737 に答える
0

あなたはすでに自分自身を理解しているので、そのn部分は明らかです。(基本的にはsize(m)の桁数) は mod によるものです。CPU が 1 つの命令でそれを実行しても、(32 ビットとしましょう) 時間がかかります。が非常に大きい場合は、暗号化キーでよくあることですが、これはかなりの量になる可能性があります。mlog(m)log(m)m

の桁数はなぜmですか? 除算を覚えておいてください:

abcdefghijk | xyz
            |-----
alm         | nrvd...
 opq
  stu
   wabc
    .......

マイナスを実行する回数は、最大で被除数の桁数です。

于 2011-10-13T00:43:01.577 に答える