数论 计算模m的k次根

计算模m的k次根

问题描述

已知   

求 x

1. 求 ϕ(m) $\varphi \left(m\right)$
2. 用欧几里得扩展求使得 ku−ϕ(m)v=1 $ku-\varphi \left(m\right)v=1$的u值
3. 用快速幂求得 x=bu（mod m） $x=b^u（modm）$

证明

xku(mod m)=xϕ(m)v+1(mod m)=x $x^{ku}\left(modm\right)=x^{\varphi \left(m\right)v+1}\left(modm\right)=x$
xku(mod m)=bu(modm) $x^{ku}\left(modm\right)=b^u\left(modm\right)$
x=bu(mod m) $x=b^u\left(modm\right)$
注意要求 gcd(k,ϕ(m))==1 $gcd(k,\varphi (m\left)\right)==1$,如果 gcd(k,phi(m))≠1 $gcd(k,phi(m\left)\right)\ne 1$ ,则说明模m的k次方根不存在或者大于一个

代码参考

// How to calculate x^k (mod p) = 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void extgcd(long long a,long long b,long long &x,long long &y)
{
    if(b == 0) x = 1,y = 0;
    else{
        extgcd(b,a%b,y,x);
        y -= a/b*x;
    }
}
long long Phi(LL n)
{
   long long ans = n;
   for(int i = 2;i < n; ++i){
      if(n%i==0) {
            ans = ans/i*(i-1);
           while(n % i == 0) n /= i;
         }
   }
   if(n != 1)
      ans = ans/n*(n-1); 
   return ans;
}
long long qpow(long long a,long long b,long long m){
    long long ans = 1;
    a %= m;
    while(b>0){
        if(b&1) ans = ans*a%m;
        a = a*a%m;
        b >>= 1;
    }
    return ans;
}

int main(void)
{
// init();
   LL x,k,b,m;
   LL xx,yy;
   while(cin>>k>>b>>m){
        long long Phim = Phi(m);
// cout<<Phim<<endl;
        extgcd(k,Phim,xx,yy); 
        xx = (xx%Phim+Phim)%Phim;
        cout<<xx<<endl;
        x = qpow(b,xx,m);
        cout<<x<<endl;
        cout<<qpow(x,k,m)<<endl;
   }
   return 0;
}