随机算法 之模幂函数

• 月黑1823 发布于
• 1741 收藏

在随机素数测试算法中要用到模幂运算，在O(lgn)的时间内产生模幂结果是非常有用的。在诸如RSA等算法中都要用到求a^n mod p的运算，例如费马小定理（a^(n-1) mod n = 1,p是a的非素数因子)及rsa算法用到的费马定理的推广(a^(y(n))mod n = 1，y(n)为n的欧拉函数)等等都需要用到模幂运算，那么怎么能快速的到模幂运算结果其实原理很简单，这是我用english写...