二次剩余-学习笔记

i207M · 2018-11-26 10:44:18 · 个人记录

二次剩余是干什么的？简单的说就是模意义下开根号：x^2=n \mod p

P为2的情况

解为x=1

P为奇素数的情况

勒让德符号：

如何求值？

定理：\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p

证明：

当a在模p意义下是二次剩余时，令x^2=a \mod p，那么就有x^{p-1}=1 \mod p，由费马小定理，显然x存在。

当a在模p意义下不是二次剩余时，依旧令x^2=a \mod p，那么就有x^{p-1}=-1 \mod p，由费马小定理，显然x不存在。

当a=0 \mod p时显然满足。

因此首先判断有解：n^{\frac{p-1}{2}} =1 \mod p

然后找到一个a，使得w=a^2-n是p的非二次剩余，答案为(a+\sqrt{w})^{p+1/2}

证明：

首先证明(a+b)^p=a^p+b^p \mod p：

由于n是质数，因此当i不等于0且不等于n的时候，组合数阶乘公式中的n是没有办法被消掉的，就会被模成0，因此这些项都是对答案没有贡献的。而i=0或i=n时，我们就分别可以得到 a^n和b^n，定理得证。

如何求a+\sqrt{w}，不是w没有二次剩余吗？

就像\sqrt{-1}一样，我们将\sqrt{w}看作类似i的存在，然后定义模意义下复数的乘法，然后快速幂即可。

如何保证最终快速幂的结果虚部为0？

根据拉格朗日定理，我们知道在任意一个模p(p\in\mathbb P)的数域里面，任意一个多项式f(x)最多有deg(f(x))个根（f(x)\equiv0\pmod p的解称为f(x)在\mathbb F_p下的根），deg表示多项式的度数，即最大指数。由于\mathbb F_{p^2}是对\mathbb F_p域的扩充，\mathbb F_p域的两根一定在\mathbb F_{p^2}内也有效，并且我们知道x^2-n在数域\mathbb F_p下的根有两个（x1,x2），那么x1,x2一定也是\mathbb F_{p^2}域下的根，也就是“虚部”系数为0。

由此问题完美解决，算法时间复杂度是O(\log p)的。

还有一个问题如何找到a？方法是随机！因为概率大概是0.5

struct F
{
    int x,y;
    F() {}
    F(const int &xx,const int &yy)
    {
        x=xx,y=yy;
    }
    friend F operator*(const F &a,const F &b)
    {
        return F(((LL)a.x*b.x%md+(LL)a.y*b.y%md*w%md)%md,((LL)a.x*b.y%md+(LL)a.y*b.x%md)%md);
    }
};
F qpow(F a,int b)
{
    F res(1,0);
    for(; b; b>>=1,a=a*a) if(b&1) res=res*a;
    return res;
}
int qpow(int a,int b)
{
    int res=1;
    for(; b; b>>=1,a=(LL)a*a%md) if(b&1) res=(LL)res*a%md;
    return res;
}
int solve(int n)
{
    if(md==2) return 1;
    if(qpow(n,(md-1)/2)==md-1) return -1;
    while(1)
    {
        int a=rand()%md;
        w=((LL)a*a%md-n+md)%md;
        if(qpow(w,(md-1)/2)==md-1)
        {
            F ans=qpow(F(a,1),(md+1)/2);
            return ans.x;
        }
    }
}

P为奇素数的幂

Blog

N次剩余

借助离散对数。

Blog