二次剩餘及其計算方法

前言

在有些時候，我們會需要求解這樣的問題 x 2 ≡ a ( m o d p ) x^2\equiv a\pmod{p} x2≡a(modp)

給定 a a a求是否有 x x x滿足這個式子，若有r則稱a是模p的二次剩餘

若沒有滿足條件的 x x x，則稱a是模p的非二次剩餘

然而在一些題目中，我們既要判定它是否是模p的二次剩餘，也要判斷其值，本文就對此進行一些探究

對于所有模數

二次剩餘數量

我們發現 a 2 ≡ ( p − a ) 2 ( m o d p ) a^2\equiv (p-a)^2\pmod p a2≡(p−a)2(modp)

是以滿足條件的二次剩餘數量不可能超過 ⌊ n 2 ⌋ + 1 \left\lfloor\frac n2\right\rfloor+1 ⌊2n​⌋+1

不同模數下的二次剩餘

模數為偶質數

顯然偶質數隻有一個，那就是2

顯然 0 0 0和 1 1 1都是 2 2 2的二次剩餘

模數為奇質數

對于判定模數為奇素數時的情況

我們定義勒讓德符号：

( a p ) = { + 1 如 果 a ̸ ≡ 0 ( m o d p ) 且 有 整 數 x 滿 足 x 2 ≡ a ( m o d p ) − 1 如 果 沒 有 整 數 x 滿 足 x 2 ≡ a ( m o d p ) 0 如 果 a ≡ 0 ( m o d p ) \left(\frac ap\right)=\begin{cases}+1&如果a\not\equiv0\pmod p且有整數x滿足x^2\equiv a\pmod p\\ -1&如果沒有整數x滿足x^2\equiv a\pmod p\\ 0&如果a\equiv0\pmod p \end{cases} (pa​)=⎩⎪⎨⎪⎧​+1−10​如果a̸​≡0(modp)且有整數x滿足x2≡a(modp)如果沒有整數x滿足x2≡a(modp)如果a≡0(modp)​

我們先引入歐拉準則

這是一個用來判定的經典準則（其實勒讓德符号的定義準确來說就是從這裡定義的）

這裡規定，當模數為奇素數的時候···（此處省略解釋）

直接代入勒讓德符号成為

( a p ) = a p − 1 2 ( m o d p ) \left(\frac ap\right)=a^{\frac{p-1}2}\pmod p (pa​)=a2p−1​(modp)

• 口糊一下證明

  由于模數是奇素數，是以我們就可以使用拉格朗日定理（ k k k次多項式至多 k k k個根）

  是以對于任意一個 a a a，滿足 x 2 ≡ a ( m o d p ) x^2\equiv a\pmod p x2≡a(modp)的 x x x數量至多為 2 2 2

  現在我們把 a = 0 a=0 a=0的情況扔掉，因為 a = 0 a=0 a=0顯然滿足上式

  隻考慮 a ≠ 0 a\neq0 a̸​=0的情況

  首先我們有費馬小定理 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv1\pmod p ap−1≡1(modp)

  由于 p p p是奇數，我們開始推式子

  移項得

  a p − 1 − 1 ≡ 0 ( m o d p ) a^{p-1}-1\equiv0\pmod p ap−1−1≡0(modp)

  因式分解得

  ( a p − 1 2 − 1 ) ( a p − 1 2 + 1 ) ≡ 0 ( m o d p ) (a^{\frac{p-1}2}-1)(a^{\frac{p-1}2}+1)\equiv0\pmod p (a2p−1​−1)(a2p−1​+1)≡0(modp)

  我們發現，如果有 x x x滿足 x 2 ≡ a ( m o d p ) x^2\equiv a\pmod p x2≡a(modp)，那麼根據費馬小定理 x p − 1 ≡ 1 ( m o d p ) x^{p-1}\equiv1\pmod p xp−1≡1(modp)

  将 x x x用 a a a代替

  a p − 1 2 ≡ 1 ( m o d p ) a^{\frac{p-1}2}\equiv1\pmod p a2p−1​≡1(modp)

  如果沒有滿足條件的 x x x，這說明

  a p − 1 2 ̸ ≡ 1 ( m o d p ) a^{\frac{p-1}2}\not\equiv1\pmod p a2p−1​̸​≡1(modp)

  則根據上面的方程，兩項中至少有一項為 0 0 0

  則 a p − 1 2 ≡ − 1 ( m o d p ) a^{\frac{p-1}2}\equiv-1\pmod p a2p−1​≡−1(modp)

  證畢

現在我們已經會如何判定了，然而OI中更多的是要求這個值（大霧）

假設我們現在已經判定完了，發現 a a a是模 p p p的二次剩餘

我們現在要求 x 2 ≡ a ( m o d p ) x^2\equiv a\pmod p x2≡a(modp)

移項得 a − 1 x 2 ≡ 1 ( m o d p ) a^{-1}x^2\equiv 1\pmod p a−1x2≡1(modp)

設 x i x_i xi​滿足 ( a − 1 x i 2 ) 2 i ≡ 1 ( m o d p ) (a^{-1}x_i^2)^{2^i}\equiv 1\pmod p (a−1xi2​)2i≡1(modp)

我們發現 x 0 x_0 x0​就是我們要求的值

我們提出 p − 1 p-1 p−1所有的 2 2 2因子： p − 1 = 2 t s p-1=2^ts p−1=2ts

我們得到一個已知的解了： x t − 1 = a s + 1 2 x_{t-1}=a^{\frac{s+1}2} xt−1​=a2s+1​

為什麼？

代入 ( a − 1 x t − 1 2 ) 2 t − 1 ≡ ( a − 1 a s + 1 ) 2 t − 1 ≡ a 2 t − 1 s ≡ a p − 1 2 ≡ 1 ( m o d p ) (a^{-1}x_{t-1}^2)^{2^{t-1}}\equiv(a^{-1}a^{s+1})^{2^{t-1}}\equiv a^{2^{t-1}s}\equiv a^\frac{p-1}2\equiv1\pmod p (a−1xt−12​)2t−1≡(a−1as+1)2t−1≡a2t−1s≡a2p−1​≡1(modp)

如果我們現在能夠遞推，那就能求答案了

首先我們發現 a − 1 x i 2 a^{-1}x_i^2 a−1xi2​是模 p p p意義下的 2 t 2^t 2t階機關根

設 a − 1 x i 2 = ω i a^{-1}x_i^2=\omega_i a−1xi2​=ωi​

我們現在已知 x i x_i xi​要遞推求 x i − 1 x_{i-1} xi−1​

由于 ω i 2 i ≡ 1 ( m o d p ) \omega_i^{2^i}\equiv1\pmod p ωi2i​≡1(modp)

是以 ω i 2 i − 1 ≡ ± 1 ( m o d p ) \omega_i^{2^{i-1}}\equiv\pm1\pmod p ωi2i−1​≡±1(modp)

• 如果 ω i 2 i − 1 ≡ 1 ( m o d p ) \omega_i^{2^{i-1}}\equiv1\pmod p ωi2i−1​≡1(modp)

  那麼可以進行指派 x i − 1 = x i x_{i-1}=x_i xi−1​=xi​

  *如果 ω i 2 i − 1 ≡ − 1 ( m o d p ) \omega_i^{2^{i-1}}\equiv-1\pmod p ωi2i−1​≡−1(modp)

  我們現在要找一個 λ \lambda λ使得 x i − 1 = λ x i x_{i-1}=\lambda x_i xi−1​=λxi​并且滿足條件 ( a − 1 ( λ x i ) 2 ) 2 i − 1 ≡ 1 ( m o d p ) (a^{-1}(\lambda x_i)^2)^{2^{i-1}}\equiv 1\pmod p (a−1(λxi​)2)2i−1≡1(modp)

  與式子 ( a − 1 x i 2 ) 2 i − 1 ≡ − 1 ( m o d p ) (a^{-1}x_i^2)^{2^{i-1}}\equiv -1\pmod p (a−1xi2​)2i−1≡−1(modp)進行聯立

  得到 λ 2 i ≡ − 1 ( m o d p ) \lambda^{2^i}\equiv-1\pmod p λ2i≡−1(modp)

  我們發現等于 − 1 -1 −1這個條件非常熟悉

  對于一個非二次剩餘 b b b， b p − 1 2 ≡ − 1 ( m o d p ) b^{\frac{p-1}2}\equiv-1\pmod p b2p−1​≡−1(modp)

  化一下式子成 − 1 ≡ b p − 1 2 ≡ b 2 t − 1 s ≡ ( b 2 t − i − 1 s ) 2 i -1\equiv b^{\frac{p-1}2}\equiv b^{2^{t-1}s}\equiv (b^{2^{t-i-1}s})2^i −1≡b2p−1​≡b2t−1s≡(b2t−i−1s)2i

  是以我們可以直接 λ = b 2 t − i − 1 s m o d    p \lambda=b^{2^{t-i-1}s}\mod p λ=b2t−i−1smodp

  至于怎麼找這個 b b b也非常簡單，直接rand即可，由于非二次剩餘占比為一半，即 T = 1 + T 2 T=1+\frac T2 T=1+2T​即 T = 2 T=2 T=2，是以是 O ( 1 ) \mathcal O(1) O(1)的

  該算法的總複雜度為 O ( l o g 2 p ) \mathcal O(log^2p) O(log2p)

  貼出代碼

const int mod=998244353;
template<typename T>
inline int pow(int x,T y)
{
    rg int res=1;x%=mod;
    for(;y;y>>=1,x=(ll)x*x%mod)if(y&1)res=(ll)res*x%mod;
    return res;
}
inline int Quadratic_residue(const int a)
{
	if(a==0)return 0;
	int b=(rand()<<14^rand())%mod;
	while(pow(b,(mod-1)>>1)!=mod-1)b=(rand()<<14^rand())%mod;
	int s=mod-1,t=0,x,inv=pow(a,mod-2),f=1;
	while(!(s&1))s>>=1,t++,f<<=1;
	t--,x=pow(a,(s+1)>>1),f>>=1;
	while(t)
	{
		f>>=1;
		if(pow((int)((ll)inv*x%mod*x%mod),f)!=1)x=(ll)x*pow(b,s)%mod;
		t--,s<<=1;
	}
	return min(x,mod-x);
}
           

先咕咕咕了，奇質數的比較常用，其它模數沒用到是以暫時不寫

貼個非常不錯的部落格的連結

我寫這篇部落格是因為我看不懂有些他寫的内容+沒有代碼

很詳細，感興趣的可以點選看看