大数取模运算Barrett reduction

• h_h8519 发布于
• 1785 收藏

Barrett reduction算法的证明和使用。 作者刚做完了课程设计作业，闲来无事写篇文章。 大数中的指数运算，需要对一个数进行取模，因为最大可能二进制下2048位的2048位次方，所以必须边做乘法边取模。 乘法使用快速幂，如果底数位数是x，指数位数是e，底数足够大的话，复杂度取决于模数，模数是m位的话，复杂度是O(m*m*e)。程序里，大数的存储是2的32次方进制的，这里的m*m要除以...