P5491

【模板】二次剩余

一个数 $a$，如果不是 $p$ 的倍数，且模 $p$ 同余某个数的平方，则称 $a$ 为模 $p$ 的二次剩余。

而一个不是 $p$ 的倍数 $b$，不同余任何数的平方，则称 $b$ 为模 $p$ 的二次非剩余。

对二次剩余求解，也就是对常数 $a$ 求解：

$$x ^ 2 \equiv a \pmod { p }$$

只讨论 $p$ 为奇素数下的情况。

定义 Legendre 符号：

$$
\left( \dfrac {a} {p} \right)
$$

当 $a$ 是模 $p$ 的二次剩余时，该值为 $1$；当 $a$ 是模 $p$ 的二次非剩余时，该值为 $-1$；当 $a$ 是 $p$ 的倍数时，该值为 $0$。

该符号满足完全积性。

欧拉判别准则：对于奇素数 $p$ 和 $p \nmid a$ 有：

$$a ^ { ( p - 1 ) / 2 } \equiv \left( \dfrac {a} {p}\right)$$

在 $1 , \cdots , p-1$ 中，恰有 $( p - 1 ) / 2 $ 个二次剩余。

设 $g$ 为 $\mathbb { F } _ p$ 的原根，则二次剩余恰好为：

$$1 , g ^ 2, g ^ 4 , \cdots , g ^ { p - 3 }$$

$xy$ 是二次剩余当且仅当 $x,y$ 都是或都不是二次剩余。

二次互反律：若 $q$ 是另一个奇素数，则有：

$$\left( \dfrac { q } { p } \right) \left( \dfrac { p } { q } \right) = ( - 1 ) ^ { ( p - 1 ) ( q - 1 ) / 4 } $$

为了快速求得一个 $x$ 满足 $x ^ 2 \equiv n \pmod { p }$，现引入 Cipolla 算法。

首先找到 $r \in \mathbb{ Z } _ p$，使得 $r ^ 2 - n $ 不是二次剩余。

可以证明满足条件的 $r$ 有 $( p - 1 ) / 2 $ 个，所以期望下 $2$ 次就能找到复合条件的 $r$。

考虑扩域 $\mathbb{ F } _ p [\sqrt { r ^ 2 - n } ]$。

也就是所有形如 $u + v \sqrt {r ^ 2 - n}$ 的数，其中 $u,v \in \mathbb{ F } _ p$。

我们记 $\alpha = \sqrt { r ^ 2 - n }$，那么域中的数即为 $u + v \alpha$。

在扩域中，有如下性质：

$( x + y ) ^ p = x ^ p + y ^ p$，可以通过二项式定理展开来说明。

$\alpha ^ p = - \alpha$，因为 $\alpha ^ p = ( r ^ 2 - n ) ^ { ( p - 1 ) / 2 } \alpha = - \alpha$。

如果 $x \in \mathbb { F } _ p$，那么仍然有 $x ^ p = x $。

现在令：

$$x = ( r + \alpha ) ^ { (p + 1 ) / 2 }$$

那么：

$$
\begin{aligned}
x ^ 2 = & ( r + \alpha ) ^ { p + 1 }
\\
= & ( r + \alpha ) ^ p ( r + \alpha )
\\
= & ( r - \alpha ) ( r + \alpha )
\\
= & r ^ 2 - \alpha ^ 2
\\
= & n
\end{aligned}
$$

也就是说此时我们在 $\mathbb { F } _ p [ \sqrt { r ^ 2 - n} ] $ 中求得了 $x ^ 2 = n$ 的一个解，可以证明 $x \in \mathbb{ F } _ p$，从而我们找到了解。

在选好 $r$ 之后，可以用数对 $( u , v )$ 表示 $u + v\alpha$。

其满足乘法规则：

$$( u _ 1 , v _ 1 ) ( u _ 2 , v _ 2 ) = ( u _ 1 u _ 2 + ( r ^ 2 - n) v _ 1 v _ 2, u _ 1 v _ 2 + u _ 2 v _ 1 )$$

代码：

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}
inline void writes(ll x) {write(x);putchar(32);}

ll T,n,p,l;

struct node{
  ll u,v;inline node(ll u=0,ll v=0):u(u),v(v){}
  inline node operator*(const node &rhs) const{
    return node((u*rhs.u%p+(v*rhs.v%p)*l%p)%p
    ,(u*rhs.v%p+v*rhs.u%p)%p);
  }
};

inline node Pow2(node b,ll p) {
  node r(1,0);while(p) {if(p&1) r=r*b;b=b*b;p>>=1;}return r;
}

inline ll Pow(ll b,ll p,ll mo) {
  ll r=1;while(p) {if(p&1) r=r*b%mo;b=b*b%mo;p>>=1;}return r;
}

inline ll rdm(ll p) {return rand()%p;}

inline ll Cipolla(ll n) {
  ll r=0;
  while(Pow((r*r-n+p)%p,(p-1)/2,p)!=p-1) r=rdm(p);
  l=(r*r-n+p)%p;
  if(!l) return r;
  else return (Pow2(node(r,1),(p+1)/2).u+p)%p;
}

int main() {

  T=read();srand((unsigned)time(0));

  while(T--) {
    n=read();p=read();
    ll legendre=Pow(n,(p-1)/2,p);
    if(legendre==p-1) {printf("Hola!\n");}
    if(legendre==0) {writeln(0);}
    if(legendre==1) {
      ll x1,x2;x1=Cipolla(n);x2=p-x1;
      if(x1>x2) swap(x1,x2);writes(x1);writeln(x2);
    }
  }

  return 0;
}