二次剩余

解方程

$$x^2 = n$$

定义一个数的 勒让德符号 为

$$\left(\frac{n}{P}\right)=\left\{\begin{array}{ll}0 & \text { if } P | n \\ 1 & \text { if } \exists a, a^{2} \equiv x(\bmod P) \\ -1 & \text { if } \text{not} \exists A a, a^{2} \equiv x(\bmod P)\end{array}\right.$$

我们只讨论$1\leq n \leq P - 1$，这个时候有

$$\left(\frac{n}{P}\right) \equiv n^{\frac{P-1}{2}} \pmod P$$

证明不难，见 ZJK 的 PTT。

我们假设$x$为非二次剩余，那么$x^{\frac{P-1}{2}} \equiv -1 \pmod P$

所以有$\sqrt x ^{P-1} \equiv -1 \pmod P$

因为证明 Lucas 定理时证明过一个结论$(a+b)^P \equiv a^P + b^P \pmod P$

所以有

$$( a + \sqrt x )^{P} \equiv a^P + \sqrt x ^ P \equiv a - \sqrt x \pmod P$$

这个形式很像平方差，我们可以再放进去一个$a + \sqrt x$，所以

$$(a + \sqrt x)^{P+1} \equiv a^2 - x \pmod P$$

于是考虑什么时候可以让$a^2 - x = n$, 那么$x = a^2 - n$。

我们假定$x = a^2 - n$并且它是一个非二次剩余，根据前面的结论，这个时候有

$$(a + \sqrt{a^2 - n})^{P+1} \equiv n \pmod P$$

那么也就是说$( a + \sqrt{a^2 - n} )^{\frac {P+1} 2} \equiv \sqrt n \pmod P$。

但是，这个东西一定是个整数吗？拉格朗日定理（我也不知道怎么证）告诉我们，$x^2 \equiv n \pmod P$最多有两个根。如果$n$存在二次剩余，那么一定是两个和为$P$的整数。所以这么求必然得到的是一个整根。

具体算法实现的话，我们随机一个$a$，判断$a^2 - n$是否为二次剩余。如果是就重新随机，否则就做一次复数的 ksm 就行了。这里的复数单位根$i$满足的是$i^2 = \sqrt{a^2 - n}$。

随机的次数我也不会证明，反正期望次数是很少的。复杂度$O(\log P)$

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 100006

int n , P;
int i2;
struct comp {
    int a , b;
    comp( int a , int b ) : a(a) , b(b) {}
};
comp operator *( comp a , comp b ) { return comp( ( 1ll * a.a * b.a % P + 1ll * a.b * b.b % P * i2 % P ) % P , ( 1ll * a.a * b.b % P + 1ll * a.b * b.a % P ) % P ); }
comp Pow( comp a , int x ) {
    comp ans( 1 , 0 );
    while( x ) {
        if( x & 1 ) ans = ans * a;
        a = a * a , x >>= 1;
    }
    return ans;
}
int work( ) {
    if( n == 0 ) return 0;
    if( P == 2 && n == 1 ) return 1;
    if( n >= P || Pow( comp(n , 0) , (P - 1) / 2 ).a == P - 1 ) return -1;
    int t;
    for( t = rand() % P + 1 ; ; t = rand() % P + 1 ) {
        i2 = ( 1ll * t * t % P - n + P) % P;
        if( Pow( comp( i2 , 0 ) , ( P - 1 ) / 2 ).a != P - 1 ) continue;
        break;
    }
    comp ans = Pow( comp( t , 1 ) , ( P + 1 ) / 2 );
    return min( ans.a , P - ans.a );
}

int main() {
    srand( time( 0 ) );
    int T;cin >> T;
    while( T-- ) {
        scanf("%d%d",&n,&P);
        int ans = work( );
        if( ans > 0 ) printf("%d %d\n",ans , P - ans);
        else if( ans == 0 ) puts( "0" );
        else puts("Hola!");
    }
}