引言

我们在研究多项式开根的时候,想到了一个问题,若常数项不为1,那么怎么开根呢?
这就涉及到二次剩余。
那么什么是二次剩余呢?若在模$p$意义下,存在一个$x$,使得$x^2 \equiv a \pmod{p}$,则称$a$为$x$关于$a$的二次剩余。若不存在这样的$x$,则称$a$为非二次剩余。
现在我们知道了$a$,要求解$x$,怎么办呢?

p为奇素数

首先引入欧拉准则
当$a$为模$p$意义下的二次剩余时,$a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$
当$a$为模$p$意义下的非二次剩余时,$a^{\frac{p-1}{2}} \equiv p-1 \pmod{p}$
我们要求的$x$满足:$(a^{-1}x^2)^{2^0} \equiv 1 \pmod{p}$
设$p-1=s2^t$,设$x _ {t-1}=a^{\frac{s+1}{2}}$,那么根据欧拉准则第一条,有:$(a^{-1}x_{t-1}^2)^{2^{t-1}} \equiv 1 \pmod{p}$
诶……要不我们设$(a^{-1}x _ {t-k}^2)^{2^{t-k}} \equiv 1 \pmod{p}$,这样我们要求的就是$x_0$
思考如何从$x _ {t-k}$推到$x _ {t-k-1}$。
设$e _ {t-k}=a^{-1}x _ {t-k}^2$
若$e _ {t-k}^{2^{t-k-1}} \equiv 1 \pmod{p}$(即将$e _ {t-k}^{2^{t-k}}$开根),显然$x _ {t-k-1}=x _ {t-k}$
若$e _ {t-k}^{2^{t-k-1}} \equiv p-1 \pmod{p}$。我们试图让$x _ {t-k}$乘一个值使得它变成$x _ {t-k-1}$。那么想到欧拉准则的第二条,首先随机一个非二次剩余$b$,然后发现$(b^{2^{k-1}s})^{2^{t-k}} \equiv p-1 \pmod{p}$,所以$b^{2^{k-1}s}$是我们满足条件的值,此时让$x _ {t-k-1}=b^{2^{k-1}s}x _ {t-k}$即可。
最后$x_0$其实有正负两个解,都满足条件。
例题:URAL 1132
代码:

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
int T,a,p,bin[22];
int ksm(int x,int y,int p) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%p) if(y&1) re=1LL*re*x%p;
    return re;
}
int jud(int x,int p) {return ksm(x,(p-1)/2,p)==1;}
void work() {
    int s=p-1,b,t=0;
    while(!(s&1)) ++t,s>>=1;
    int inva=ksm(a,p-2,p),e=ksm(a,s,p),x=ksm(a,(s+1)/2,p);
    while("xzy is too strong") {
        b=rand()%p+1,b=((b*b-a)%p+p)%p;
        if(b&&!jud(b,p)) break;
    }
    for(RI k=1;k<t;++k)
        if(ksm(e,bin[t-k-1],p)!=1)
            x=1LL*x*ksm(b,bin[k-1]*s,p)%p,e=1LL*inva*x%p*x%p;
    int x1=x,x2=p-x;
    if(x1>x2) swap(x1,x2);
    printf("%d %d\n",x1,x2);
}
int main()
{
    srand(19260817);
    T=read();
    bin[0]=1;for(RI i=1;i<=20;++i) bin[i]=bin[i-1]<<1;
    while(T--) {
        a=read(),p=read();
        if(p==2) {puts("1");continue;}
        if(!jud(a,p)) {puts("No root");continue;}
        work();
    }
    return 0;
}

p为奇素数的幂

求满足$x^2 \equiv a \pmod{p^q}$的$x$。
设$a=p^kd$。
显然答案是$x=p^{\frac{k}{2}}x_0$的形式。
则$p^k x _ 0^2 \equiv p^k d \pmod{p^q}$,也就是说$(d-x _ 0^2)p^k \equiv 0 \pmod{p^q}$,那么有$(d-x _ 0^2) \equiv 0 \pmod{p^{q-k}}$
问题转化为求$x _ 0^2 \equiv d \pmod{p^{q-k}}$,而$d$与$p$是互质的。
为了方便起见,假设我们现在要求解的问题是$x^2 \equiv a \pmod{p^q}$,$a$与$p$互质。

找到一个模$p^q$的简化剩余系下的原根$g$,我们就可以用$g^r(1 \leq r \leq \phi(p^q))$来表示所有在模$p^q$意义下与$p^q$互质的数。
当$r$为奇数时,设存在$g^r \equiv g^{2m} \pmod{p^q}$。也就是$r \equiv 2m \pmod{\phi(p^q)}$,也就是$r=2m+k\phi(p^q)$。
我们知道$\phi(p^q)=(p-1)p^{q-1}$,又因为$p$是奇素数,所以$\phi(p^q)$是偶数,所以$2m+k\phi(p^q)$也是偶数。而$r$是奇数,所以显然找不到这样的$m$。
当然因为$g$肯定是与$p$互质的,所以$g^r \equiv g^{2m}p^t \pmod{p^q}$也是不可能成立的啦。所以此时$g^r$是个二次非剩余啦。
而当$r$为偶数的时候,显然$g^r$是个二次剩余啦。

对于任意二次剩余$g^{2k}$,有
$$(g^{2k})^{\frac{\phi(p^q)}{2}} = (g^k)^{\phi(p^q)} \equiv 1 \pmod{p^q}$$
对于任意二次非剩余$g^{2k+1}$有:
$$(g^{2k+1})^{\frac{\phi(p^q)}{2}} \equiv g^{\frac{\phi(p^q)}{2}} \pmod(p^q)$$
我们知道$g^{\frac{\phi(p^q)}{2}}$与$g^{\phi(p^q)}$肯定不相等,而后者等于1,前者是后者的开根,所以等于-1。
我们得到了一个new欧拉准则。
求解时,先将问题转化为$a$与$p$互质,然后令$\phi(p^q)=s2^t$,套用p为奇素数时的求解方法即可。

p为2的幂

这个嘛……同样,化一下,令$a=2^kd$,那么求解$x _ 0^2 \equiv d \pmod{2^{q-k}}$,然后解就是$x=2^{\frac{k}{2}}(x _ 0+2^{q-k}t)$的形式。
然后我们知道,当$q=1$的时候,当$a=1$时有解$x=1$
当$q=2$时,当$a=1$时有解$x=1,x=3$
当$q=3$时,当$a=1$时有解$x=1,x=3,x=5,x=7$
我们将$q=k$意义下解的形式写成$x _ k= \pm (y _ k+t _ k 2^{k-1})$。记$a_k = a \bmod{2^k}$
继续推,现在我们已知了$x _ {k-1}\equiv\pm(y _ {k-1}+t _ {k-1}2^{k-2}) \pmod{2^{k-1}}$
那么$x _ {k-1}^2$在模$2^k$意义下可能是$a _ {k-1}$或$a _ {k-1}+2^{k-1}$。我们在现在符合条件的若干$t _ {k-1}$值中选择出能使$x _ {k-1}^2 \equiv a _ k \pmod{2^k}$的,然后:
$$(y _ {k-1}+t _ {k-1}2^{k-2})^2 \equiv a _ k \pmod{2^k}$$
将左边的式子拆开,得到$y _ {k-1}^2 + t _ {k-1}2^{k-1}y _ {k-1}+t _ {k-1}^2 2^{2k-4}$,由于我们之前已经保证过了$a$是奇数,所以$y$一定是奇数,而我们知道$t_{k-1}2^{k-1} \times 2 \equiv 0 \pmod{2^k}$所以第二项一定等于$t_{k-1}2^{k-1}$。第三项则一定等于0。
所以
$$y _ {k-1}^2 + t _ {k-1}2^{k-1} \equiv a _ k \pmod{2^k}$$
$$t _ {k-1}2^{k-1} \equiv a _ k -y _ {k-1}^2 \pmod{2^k}$$
$$t _ {k-1} \equiv \frac{a _ {k} – y _ {k-1}^2}{2^{k-1}} \pmod{2}$$
所以设$t _ {k-1}= \frac{a _ {k} – y _ {k-1}^2}{2^{k-1}} + 2 t _ k$,那么
$$x _ k = \pm (y _ {k-1}+\frac{a _ k- y _ {k-1}^2}{2} + 2^{k-1}t _ k)$$
也就是说,$y _ k=y _ {k-1}+\frac{a _ k- y _ {k-1}^2}{2}$
所以我们就从$q=3$开始不断往上推,就可以出解了。

p为合数

嗯,将p质因数分解,然后分别求解,中国剩余定理合并即可。

分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *