二次剩余小记 更新于 2026/7/10 08:43:43 作者

command_block

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$了。

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

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

二次剩余的个数

$\color{blue}\text{结论:}$ 模$p$下的二次剩余恰有$\dfrac{p-1}{2}$个。

• 引理 : $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;
}