algorithm - 2^n mod (m) 算法

Question

在类里面，我们学习了 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 部分，但我无法解释 size(m) 除非是因为涉及减法。任何人都可以阐明这一点吗？

提前致谢。

Answer 1

n 部分很清楚，因为您已经了解了自己。 size(m)(这是 m 中的位数，基本上是 log(m))是因为 mod。即使您的 CPU 在一条指令中为您执行此操作，它也需要 log(m)(假设是 32 位)次。如果 m 非常大，这在加密 key 中很常见，这可能会变得相当大。

为什么 m 中的位数？记住除法:

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

减的次数最多为被除数的位数。