二次剩余小记

command_block · 2019-08-19 13:22:43 · 个人记录

P.S 本文只探讨模数p是奇质数的情况。

目标/定义

求解 \large{x^2=c(mod\ p)} 这个方程组。

如果方程有解,则称c是模p的二次剩余,否则称作二次非剩余。

(下面默认在模p的剩余系下讨论)

欧拉判别法

给定c,p,如何判定 x^2=c 是否有解呢?

\color{blue}\text{结论:}$ $c^{\large{\frac{p-1}{2}}}=\begin{cases}\ \ \ 1\rightarrow\text{有解}\\ -1\rightarrow\text{无解}\end{cases}

\color{blue}\text{证明:}

引理\color{blue}1.1 : c^{\large{\frac{p-1}{2}}}=±1

由费马小定理得(c^{\large{\frac{p-1}{2}}})^2=c^{p-1}=1,可得c^{\large{\frac{p-1}{2}}}=±1

引理\color{blue}1.2 c^{\large{\frac{p-1}{2}}}=-1 \Rightarrow c不是二次剩余

采用反证法,假设有x^2=c,可得c^{\large{\frac{p-1}{2}}}=x^{p-1}=-1

与费马小定理矛盾,原命题得证。

引理\color{blue}1.3 c^{\large{\frac{p-1}{2}}}=-1 \Leftarrow c不是二次剩余

假设有x^2=c,但是x不是同余系里面的数,可以视为虚数,只满足x^2=c这一条性质。

由于x不是同余系内的数,必定不满足费马小定理,可得x^{p-1}≠1,那么只能是-1了。

(费马小定理对且只对同余系生效)

综上三个引理可以逻辑推导出欧拉判别法,证毕。

二次剩余的个数

- 引理 : $c^2=(p-c)^2

显然成立,由此可得,如果x^2=c有解,则必然有两解。

\color{blue}\text{证明:}

任选两个数x,y(x≠y),且x^2=y^2

那么(x+y)(x-y)=0,即p|(x+y)(x-y),

显然p|(x-y)不成立,那么p|(x+y),即x+y=0。

那么,对于一个x,和它平方相同的有且仅有另外一个y。

总共有\dfrac{p-1}{2}个不同的平方,那么二次剩余,二次非剩余各有\dfrac{p-1}{2}个。

Cipolla算法

现在真正来求解x^2=c(mod\ p)

首先判定方程是否无解(如果c=0则输出0)

如果有解,我们任意找一个a,使得a^2-c是二次非剩余。

方法:不断随机然后判定。根据上文内容,期望随机次数2次。

设w^2=(a^2-c),注意w不是同余系里面的数,可以理解为虚数,只有w^2=(a^2-c)这一条性质。

我们扩系,把每个数变成a+bw的形式,重载运算。容易证明扩系之后仍然是环。

P.S 设s=w^2=(a^2-c)
(x_1+y_1w)*(x_2+y_2w)=(x_1x_2+y_1y_2s)+(x_1y_2+x_2y_1)w

那么c=(a+w)^{p+1},所以x=(a+w)^{\frac{p+1}{2}}

引理\color{blue}3.1 (a+b)^p=a^p+b^p

二项式展开可得 : (a+b)^p=\sum\limits_{i=0}^p\dbinom{i}{p}a^{i}b^{p-i}

由卢卡斯定理 : \dbinom{i}{p}=\dbinom{i/p}{p/p}\dbinom{i\%p}{p\%p}=\dbinom{i/p}{1}\dbinom{i\%p}{0}

这个式子只在i=0或者p的时候值为1,否则为0.

所以(a+b)^p=a^p+b^p
引理\color{blue}3.2 w^p=-w
w^p=w^{p-1}w=(a^2-c)^{\large{\frac{p-1}{2}}}w
由欧拉判别法,(a^2-c)^{\large{\frac{p-1}{2}}}=-1,证毕。

那么 :

(a+w)^{p+1}=(a^p+w^p)(a+w)=(a+w)(a-w)

=a^2-w^2=a^2-a^2+c=c

正确性得证。

P5491 【模板】二次剩余

#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
int mod,c;
ll powM(ll a,int t)
{
  ll ans=1;
  while(t){
      if (t&1)ans=ans*a%mod;
      a=a*a%mod;
      t>>=1;
  }return ans;
}
ll sav;
struct Mcp
{ 
  ll x,y;
  Mcp operator * (Mcp const& B) const
  {return (Mcp){(x*B.x+y*B.y%mod*sav)%mod,(x*B.y+y*B.x)%mod};}
};
Mcp powM(Mcp a,int t)
{
  Mcp ans=(Mcp){1,0};
  while(t){
      if (t&1)ans=ans*a;
      a=a*a;
      t>>=1;
  }return ans;
}
void solve()
{
  scanf("%d%d",&c,&mod);
  if (c==0)
    {puts("0");return ;}
  if (powM(c,(mod-1)/2)==mod-1)
    {puts("Hola!");return ;}
  int a;
  while(1){
    a=(rand()%(mod-1)+mod)%(mod-1)+1;
    sav=(1ll*a*a-c+mod)%mod;
    if (powM(sav,(mod-1)/2)==mod-1){
      Mcp W=(Mcp){a,1};
      W=powM(W,(mod+1)/2);
      ll x1=W.x,x2=mod-W.x;
      if (x1>x2)swap(x1,x2);
      printf("%lld %lld\n",x1,x2);
      break;
    }
  }
}
int main()
{
  int T;
  scanf("%d",&T);
  while(T--)solve();
  return 0;
}