快速幂取模的计算复杂度

2019-04-13 21:44发布

站内文章 / 模拟电子
13858 0 971
背景：RSA加密算法：C=M^e mod n 的计算复杂度 计算原理及步骤
  1. M^emod n=(Mmod n)^e mod n，故将M缩小至n的余数范围内
  2. （最核心的思想） 不断的将M变为M^2，举个例子：M^{19}equiv (M^2)^8 imes Mequiv ((M^2)^2)^4 imes M mod n，这样的话每一次就只需要计算M^2mod n，每一步省一半的计算量
  3. 但如果某一步的e是奇数，就把它直接算到C里面
从第二步可以看出，算法的复杂度是O(log e)的 int C = 1; M = M % n; while(e != 0){ if(e & 1) C = (C * M) % n; e>>=1; M = (M*M) % n; }  

热门文章