计算模m的k次根

问题描述

已知   

g c d ( b , m ) = 1 , g c d ( k , ϕ ( m ) ) = 1
x k = b ( m o d <mtext>   </mtext> m )

求 x

  1. 求 ϕ ( m )
  2. 用欧几里得扩展求使得 k u − ϕ ( m ) v = 1 的u值
  3. 用快速幂求得 x = b u （ m o d <mtext>   </mtext> m ）

证明

x k u ( m o d <mtext>   </mtext> m ) = x ϕ ( m ) v + 1 ( m o d <mtext>   </mtext> m ) = x
x k u ( m o d <mtext>   </mtext> m ) = b u ( m o d m )
x = b u ( m o d <mtext>   </mtext> m )
注意要求 g c d ( k , ϕ ( m ) ) == 1 ,如果 g c d ( k , p h i ( m ) ) ≠ 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;
}