二次剩余

對于素數 $p$ 和數 $a$，滿足 $(a,p)=1$。（注意 $a$ 不一定小于 $p$）

若 ${?}_x{x}^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$，則稱 $a$ 是模 $p$ 意義下的二次剩余，$x$ 稱為該二次剩余方程式的解。

否則稱 $a$ 是模 $p$ 意義下的非二次剩余。

特判掉 $p=2$ 的情況，接下來默認 $p$ 均為非 $2$ 質數，即奇素數。

勒讓德符號

定義：
$$\left(\frac{a}{p}\right)=?\begin{array}{l}0p|a\\ 1a在(\mathrm{m}\mathrm{o}\mathrm{d}p)意義下是二次剩余\\ ?1a在(\mathrm{m}\mathrm{o}\mathrm{d}p)意義下不是二次剩余\end{array}$$

歐拉準則

$$\left(\frac{a}{p}\right)\equiv a^{\frac{p?1}{2}}(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

證明：

• $p|a$。顯然成立。

• 當 $a$ 是在模 $p$ 意義下的二次剩余。

  即 ${?}_x{x}^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

  有 $(x^2{)}^{\frac{p?1}{2}}\equiv a^{\frac{p?1}{2}}(\mathrm{m}\mathrm{o}\mathrm{d}p)?x^{p?1}\equiv a^{\frac{p?1}{2}}(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

  $\because (a,p)=1\therefore (x,p)=1$。

  $?x^{p?1}\equiv 1\equiv a^{\frac{p?1}{2}}(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

• 當 $a$ 在模 $p$ 意義下不是二次剩余。

  則有 ${?}_{i\in [1,p)}ij\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$ 的 $j$ 是唯一的，且 $j=i$。

  考慮用證明逆元唯一的思路來證明這里的唯一性。反證法。

  假設 $0<j_1<j_2<p$ 滿足 $i{j}_1\equiv i{j}_2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

  則 $i(j_2?j_1)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)?p|i(j_2?j_1)$。

  $(i,p)=1?p|(j_2?j_1)$，與 $0<j_2?j_1<p?(j_2?j_1,p)=1$ 矛盾。

  $p?1$ 是偶數，那么我們考慮可以把這些數兩兩配對，配出 $\frac{p?1}{2}$ 對。

  即 $a^{\frac{p?1}{2}}\equiv (p?1)!\equiv ?1(\mathrm{m}\mathrm{o}\mathrm{d}p)$（威爾遜定理）。

---

換言之：

$x^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p),(a,p)=1$。

$a^{\frac{p?1}{2}}\equiv \pm 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

方程有解當且僅當 $a^{\frac{p?1}{2}}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

Cipolla

lemma ：設 $\omega$ 不是模 $p$ 的二次剩余，即 ${?}_x{x}^2\equiv \omega (\mathrm{m}\mathrm{o}\mathrm{d}p)$，且 $\omega =t^2?a$。則 $x=(t+\sqrt{\omega }{)}^{\frac{p+1}{2}}$ 是二次剩余方程 $x^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$ 的解。

證明：

$(t+\sqrt{\omega }{)}^p={\sum }_{i=0}^p(\genfrac{}{}{0ex}{}{p}{i})t^i(\sqrt{\omega }{)}^{p?i}=t^p+{\omega }^{\frac{p}{2}}+{\sum }_{i=1}^{p?1}\left(\genfrac{}{}{0ex}{}{p}{i}\right)t^i(\sqrt{\omega }{)}^{p?i}$。

$i\in (0,p),\left(\genfrac{}{}{0ex}{}{p}{i}\right)=\frac{p!}{i!(p?i)!}$。

組合數是整數，$i!,(p?i)!$ 里的每個數都 $<p$，又 $p$ 是奇素數，所以 $i!,(p?i)!$ 里面均不會篩到 $p$。

所以 $p\left|\right(\genfrac{}{}{0ex}{}{p}{i})$。也就是說后面的求和在模 $p$ 意義下是 $0$。

$?(t+\sqrt{\omega }{)}^p\equiv t^p+(\sqrt{\omega }{)}^p(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

$t^p+(\sqrt{\omega }{)}^p=t^p+{\omega }^{\frac{p?1}{2}}\sqrt{\omega }$，因為 $\omega$ 不是模 $p$ 意義下的二次剩余，所以 $\left(\frac{\omega }{p}\right)=?1={\omega }^{\frac{p?1}{2}}$，$t^p=t^{p?1}t\equiv t(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

$?(t+\sqrt{\omega }{)}^p\equiv t?\sqrt{\omega }(\mathrm{m}\mathrm{o}\mathrm{d}p)$

$x^2\equiv (t+\sqrt{\omega }{)}^{p+1}\equiv (t+\sqrt{\omega }{)}^p(t+\sqrt{\omega })\equiv (t?\sqrt{\omega })(t+\sqrt{\omega })\equiv t^2?\omega \equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

在算法實現中，隨機 $t$ 后求 $\omega$，大約有一半的數都是非二次剩余。期望兩次便可求出 $x$。

---

考慮另一種二次剩余方程：$x^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}{p}^n)$，其中 $(a,p)=1$，$p$ 為奇質數。

先求出 $x^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$ 的一個解 $\tau$，有 ${\tau }^2?a=kp?({\tau }^2?a{)}^n\equiv k^n{p}^n\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^n)$。

$\{\begin{array}{l}(r+\sqrt{a}{)}^n=f+g\sqrt{a}\\ (r?\sqrt{a}{)}^n=f?g\sqrt{a}\end{array}$

兩個式子的結果答案長相一定可以這么寫。

證明：二項式定理展開 $\left(\genfrac{}{}{0ex}{}{n}{i}\right){\tau }^{n?i}(\pm \sqrt{a}{)}^i$，$(\pm \sqrt{a}{)}^i$ 如果 $i$ 是偶數，第 $i$ 項就在 $f$ 里面，否則就在 $g$ 里面。

也就是說，$({\tau }^2?a{)}^n\equiv [(\tau +a)(\tau ?a){]}^n\equiv (\tau +a{)}^n(\tau ?a{)}^n\equiv (f+g\sqrt{a})(f?g\sqrt{a})\equiv f^2?g^{2}a\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}^n)$。

$(f,p)=1,(g,p)=1?f^2\text{inv}(g^2)\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}n)$。

由于 $p^n$ 不是質數，所以用 $\text{exgcd}$ 求逆元即可。

代碼

#include <cstdio> #include <iostream> #include <ctime> #include <random> using namespace std; #define int long long int T, n, p, omega; mt19937 wwl(time(0));struct complex {int x, y;complex(){}complex( int X, int Y ) { x = X, y = Y; }complex operator * ( complex v ) {int ansx = ( x * v.x % p + y * v.y % p * omega % p ) % p;int ansy = ( x * v.y % p + y * v.x % p ) % p;return complex( ansx, ansy );} };int qkpow( complex x, int y ) {complex ans( 1, 0 );while( y ) {if( y & 1 ) ans = ans * x;x = x * x;y >>= 1;}return ans.x; }int qkpow( int x, int y, int mod ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }int cipolla( int n, int p ) {n %= p;if( p == 2 ) return n;if( qkpow( n, p - 1 >> 1, p ) == p - 1 ) return -1;int t;while( 1 ) {t = wwl() % p;omega = ( ( t * t % p - n ) % p + p ) % p;if( qkpow( omega, p - 1 >> 1, p ) == p - 1 ) break;}complex ans( t, 1 );return qkpow( ans, p + 1 >> 1 ); }signed main() {scanf( "%lld", &T );while( T -- ) {scanf( "%lld %lld", &n, &p );if( n == 0 ) { puts("0"); continue; }int ans = cipolla( n, p );if( ! ~ ans ) { puts("Hola!"); continue; }if( ans == p - ans ) printf( "%lld\n", ans );else printf( "%lld %lld\n", min( ans, p - ans ), max( ans, p - ans ) );}return 0; }

總結

以上是生活随笔為你收集整理的[学习笔记] 二次剩余的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。