在类里面,我们学习了 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) 除非是因为涉及减法。任何人都可以阐明这一点吗?
提前致谢。
最佳答案
n
部分很清楚,因为您已经了解了自己。 size(m)
(这是 m
中的位数,基本上是 log(m)
)是因为 mod。即使您的 CPU 在一条指令中为您执行此操作,它也需要 log(m)
(假设是 32 位)次。如果 m
非常大,这在加密 key 中很常见,这可能会变得相当大。
为什么 m
中的位数?记住除法:
abcdefghijk | xyz
|-----
alm | nrvd...
opq
stu
wabc
.......
减的次数最多为被除数的位数。
关于algorithm - 2^n mod (m) 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7747946/