原根与指标

指数与原根

$$a^e\equiv 1(modm)$$

对于上面这个式子

成立的最小整数e对模m的指数，记做$or{d}_m(a)$。

如果a对模m的指数是$\phi （m）$,则a叫做模m的原根（原根不唯一）。

作用：原根的求解只是求解高次同余方程时计算指标，判断是否有解。

定理5.2.1

设p是奇素数，则模p的原根存在，且有$\phi （p-1）$个原根。

定理5.2.2

设p为奇素数，p-1的所有不同素因子为$q_1,\dots \dots ,q_s$则g是模p的原根的充要条件是：
$$g^{\frac{p-1}{q_i}}!\equiv 1(modp),i=1,\dots \dots ，s$$

例题求模p=43的原根$P_{180}$

1. 得到p-1
2. 计算$q_i$（为p-1的素因子）
3. 将g=2,3,5,6,7等带入计算，逐个验证,根据定理5.2.2进行判断。

PS

在进行第三部的时候可以通过求其平方的方法进行迭代，或者其他一些小trick

指标

$$g^r\equiv a(modm)$$

对于上式来说：

• g是模m的一个原根
• a是一个与m互素的整数
• 存在唯一一个整数r使上式成立

这个整数r叫做以g为底的a对模m的一个指标，记作$r=in{d}_{g}a(或r=inda)$

当我们了解了原根与指标的计算之后就可以进行高次同余方程的学习了

高次同余方程判断是否有解

参考$P_{196}$
$$x^n\equiv a(modm)$$
对于这个高次同余式，有解的条件是满足$（n,\phi （m））|inda$，且解数为$（n,\phi （m））$

原根的求解只是求解高次同余方程时计算指标，判断是否有解

所以我们可以记住常见的模p对应的原根：

在考试的时候直接写出，然后验证其是原根既可。

得到了原根，我们就可以根据公式三进行计算，得到对应的指标。

要求学会画对应的指标表，听说模数小的会让我们求，模数大的会提供一个对应的指标表。

根据$（n,\phi （m））|inda$进行判断，且解数为$（n,\phi （m））$
$$x^{12}\equiv 37(mod41)$$
判断出有解之后进行化简：

mod $\phi （41）$
$$\begin{gathered} 12indx\equiv ind37(mod\phi (41)) \\ =>12indx\equiv 32(mod40) \\ =>3indx\equiv 8(mod10) \end{gathered}$$
自己计算得到一个特殊解:$indx=6$

然后计算特解：
$$indx=6+k\times 10(mod40)k\in Z$$
既可得出$indx\equiv 6,16,26,36(mod40)$

通过查表求出对应的$x\equiv 39,18,2,23(mod41)$

求解的过程类似于一次同余式：

通过查表求出对应的$x\equiv 39,18,2,23(mod41)$

求解的过程类似于一次同余式：

/*

解高次同余方程

A^x ≡ B( mod C )

c非素数
POJ 3243
*/

#include <iostream>
#include <cstdio>
#include<cmath>
//#define maxn 65535

using namespace std;

const int maxn=65535;

struct hash
{
    int a,b,next;
}Hash[maxn*2];

int flg[maxn+66];
int top,idx;

void ins(int a,int b)
{
    int k=b&maxn;
    if(flg[k]!=idx)
    {
        flg[k]=idx;
        Hash[k].next=-1;
        Hash[k].a=a;
        Hash[k].b=b;
        return ;
    }
    while(Hash[k].next!=-1)
    {
        if(Hash[k].b==b) return ;
        k=Hash[k].next;
    }
    Hash[k].next=++top;
    Hash[top].next=-1;
    Hash[top].a=a;
    Hash[top].b=b;
}

int find(int b)
{
    int k=b&maxn;
    if(flg[k]!=idx) return -1;
    while(k!=-1)
    {
        if(Hash[k].b==b)
            return Hash[k].a;
        k=Hash[k].next;
    }
    return -1;
}

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

int exgcd(int a,int b,int& x,int& y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int r,tx,ty;
    r=exgcd(b,a%b,tx,ty);
    x=ty;
    y=tx-a/b*ty;
    return r;
}

int inval(int a,int b,int n)
{
    int x,y,e;
    exgcd(a,n,x,y);
    e=(long long )x*b%n;
    return e<0?e+n:e;
}

int pow_mod(long long a,int b,int c)
{
    long long ret=1%c;
    a%=c;
    while(b)
    {
        if(b&1)
            ret=ret*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ret;
}

int babystep(int A,int B,int C)
{
    top=maxn;++idx;
    long long buf=1%C,D=buf,K;
    int d=0,tmp;
    for(int i=0;i<=100;buf=buf*A%C,i++)
        if(buf==B)
            return i;
    while((tmp=gcd(A,C))!=1)
    {
        if(B%tmp) return -1;
        ++d;
        C/=tmp;
        B/=tmp;
        D=D*A/tmp%C;
    }
    int M=(int)ceil(sqrt((double)C)),i;
    for(buf=1%C,i=0;i<=M;buf=buf*A%C,i++) ins(i,buf);
    for(int i=0,K=pow_mod((long long)A,M,C);i<=M;D=D*K%C,i++)
    {
        tmp=inval((int)D,B,C);
        int w;
        if(tmp>=0&&(w=find(tmp))!=-1)
            return i*M+w+d;
    }
    return -1;
}

int main()
{
    int A,B,C;
    while(scanf("%d%d%d",&A,&B,&C)!=EOF,A||B||C)
    {
        B%=C;
        int tmp=babystep(A,B,C);
        if(tmp<0)
            printf("No Solution\n");
        else
            printf("%d\n",tmp);
    }
    return 0;
}

/*
解高次同余方程

A^x ≡ B( mod C )

c  是素数
时间复杂度O(sqrt(n)*logn)
POJ 2471

*/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
//快速幂求a^b
LL pow_mod(LL a,LL b,LL n)
{
    LL s=1;
    while(b)
    {
        if(b&1)
            s=(s*a)%n;
        a=(a*a)%n;
        b=b>>1;
    }
    return s;
}
//求解模方程a^x=b(mod n)。n为素数，无解返回-1
//费马小定理a^(n-1)=1(mod n),n为素数。a^0=1,所以循环节小于等于n，即如果存在解，则最小解x<=n
LL log_mod (LL a,LL b,LL n)
{
    LL m,v,e=1,i;
    m=ceil(sqrt(n+0.5));     //x=i*m+j
    //v=inv(pow_mod(a,m,n),n);  //a^m*v=1(mod n)
    v=pow_mod(a,n-m-1,n);
    map<LL,LL>x;
    x[1]=m;
    for(i=1;i<m;i++)  //建哈希表，保存x^0,x^1,...,x^m-1
    {
        e=(e*a)%n;
        if(!x[e])x[e]=i;
    }
    for(i=0;i<m;i++)//每次增加m次方，遍历所有1<=x<=n
    {
        if(x[b])
        {
            LL num=x[b];
            x.clear();//需要清空，不然会爆内存
            return i*m+(num==m?0:num);
        }
        b=(b*v)%n;   //b=b/(a^m)
    }

    return -1;
}
int main()
{
    LL a,b,n;
    while(scanf("%I64d%I64d%I64d",&n,&a,&b)!=EOF)
    {
        LL ans=log_mod(a,b,n);
        if(ans==-1)printf("no solution\n");
        else printf("%I64d\n",ans);
    }
    return 0;
}