大家好，欢迎来到IT知识分享网。

概念１：原根

欧拉定理：

设m是大于1的整数,（a,m）=1,则a^φ(m)=1(mod m).  注:(a,m)表示a和m的GCD.

也就是说，若（a,m）=1,m>1,则至少存在一个正整数r,满足a^r=1(mod m).

指数的定义：

若m>1,(a,m)=1,则使得同余式a^r=1(mod m)成立的最小正整数r叫做a对于模m的指数(阶),记r为ordm(a).

定理1:若(a,m)=1,m>0,则x是 a^x=1(mod m) 的解的充要条件是：ordm(a)|x.

定理2:若(a,m)=1,m>0,则a^i=a^j(mod m),当且仅当i=j(mod ordm(a)),其中i,j是非负整数.

推论：若(a,m)=1,m>0,则ordm(a)|φ(m).

原根的定义：

若(a,m)=1,m>0,且ordm(a)=φ(m),则a称为模m的一个原根.

注：并不是所有的模m都存在原根.

指数的性质：

性质1:若x对于模m的指数是ab,a>0,b>0,则x^a对于模m的指数是b.

性质2:若x对于模m的指数是a,y对于模m的指数是b，并且(a,b)=1,1),则xy对于模m的指数是ab.

原根的性质:

性质1: 若(a,m)=1,m>0,如果a是模m的一个原根，则a^0,a^1,a^2…,a^φ(m)构成模m的简化剩余类
.

原根求法：

问题：求一个mod p意义下的原根（p为素数）

原理：由于最小原根通常较小, 可以通过从小到大枚举正整数来快速寻找一个原根.

         对p-1的每个素因子a，检查g^((p-1)/a)=1(mod p)是否成立，如果成立则说明不是原根

模板：

//求原根  
vector<LL>a;  
bool g_test(LL g,LL p)  
{  
    for(LL i=0;i<a.size();i++)  
    {  
        if(pow_mod(g,(p-1)/a[i],p)==1)  
            return 0;  
    }  
    return 1;  
}  
LL primitive_root(LL p)  
{  
    LL tmp=p-1;  
    a.clear();  
    for(LL i=2;i<=tmp/i;i++)  
    {  
        if(tmp%i==0)  
        {  
            a.push_back(i);  
            while(tmp%i==0)  
                tmp/=i;  
        }  
    }  
    if(tmp!=1)  
        a.push_back(tmp);  
    LL g=1;  
    while(true)  
    {  
        if(g_test(g,p))  
            return g;  
        g++;  
    }  
}

概念2：离散对数

部分转载自http://blog.csdn.net/acdreamers/article/details/9767947

离散对数是一种在整数中基于同余运算和原根的对数运算.

离散对数的定义：

设g是模m的一个原根，对已知的a，存在整数r，使得 g^r=a (mod m)成立,

则称r为以g为底的a对模m的一个离散对数。记作r=dlog(a)。

离散对数的性质：

当模有原根时,设为模的一个原根，则当时，。

此处的是以整数为底模的离散对数值。

应用：

问题１：给定A,B,C,求同余方程的解，其中是素数。

问题２：给定Ｘ,B,C,求同余方程的解，其中是素数。

分析：利用离散对数的知识，先求模的一个原根，那么就有。

     对于，用Baby Step Giant Step能很好地解决.

     那么这样我们再用扩展欧几里得算法可以计算出A或者，快速幂再进一步求，所以就可以完美解决。

那么，如果为合数呢？

其实，如果为合数，我们要做的第一件事就是把素因子分解，即，

那么我们分别计算，然后用CRT(中国剩余定理)合并即可。

那么对于，有两种情况：

（1）

（2）

对于情况（1），我们就直接先求原根，然后利用离散对数来解决。

而对于情况（2），我们有，这样就转化为情况（1）了。

假设对于每个的解的个数为，那么方程的解的个数为。

baba-step

LL pow_mod(LL a,LL p,LL n)
{
    LL ans=1;
    while(p)
    {
        if(p&1)
            ans=(ans*a)%n;
        p>>=1;
        a=(a*a)%n;
    }
    return ans;
}
void gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(!b) { d=a; x=1; y=0; }
    else
    {
        gcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
LL inv(LL a,LL n)
{
    LL d,x,y;
    gcd(a,n,d,x,y);
    return d==1 ? (x+n)%n : -1;
}
int log_mod(int a,int b,int n)
{
    int m,v,e=1,i;
    m=(int)sqrt(n+0.5);
    v=inv(pow_mod(a,m,n),n);
    map<int,int> x;
    x[1]=0;
    for(i=1;i<m;i++)
    {
        e=e*a%n;
        if(!x.count(e))
            x[e]=i;
    }
    for(int i=0;i<m;i++)
    {
        if(x.count(b))
            return i*m+x[b];
        b=b*v%n;
    }
    return -1;
}