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) 除非是因为涉及减法。任何人都可以对此有所了解吗？

提前致谢。

score 0 · Accepted Answer

我相信这用于密码学（所谓的不可逆函数）。

如果我们需要(2**n) mod m递归计算，这将是最明显的方法。由于递归的深度是n，O(n)复杂性是显而易见的。

但是，如果我们想支持任意大小的m（512 位密钥在密码学中是可能的，并且比任何算术寄存器都大得多），我们还应该考虑到（在大多数情况下我们不必使用任意精度的算术，所以这个术语通常是 1)。

编辑@Mysticial：该函数没有mod明确调用硬件操作，它所做的只是移位和减法。shift 总是O(1)在加法/减法时O(ceil(m/sizeof_ALU_precision))

score 0 · Accepted Answer

这n部分很清楚，因为您已经了解自己。（这size(m)是中的位数m，基本上是log(m)）是因为 mod。即使您的 CPU 在一条指令中为您执行此操作，也需要log(m)（比如说 32 位）时间。如果m非常大，就像加密密钥一样，这可能会变得相当大。

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

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

你做减号的次数最多是被除数的位数。

2 回答 2