ReZero's Utopia.

数论(指数取余)

Word count: 130Reading time: 1 min
2016/11/19 Share

费马小定理(Fermat Theory)是数论中的一个重要定理,其内容为: 假如p是质数,且gcd(a,p)=1,那么
a(p-1)≡1(mod
p)。即:假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。


蒙哥马利幂模运算
RSA算法的核心之一

long long pows(int a, int b, int mod){
    long long temp = 1;
    while(b){
        if(b%2){
            temp = temp*a%mod;
        }
        a = a*a%mod;
        b/=2;
    }
    return temp;
}
CATALOG