

二次剩余

一个数，如果不是的倍数且模同余于某个数的平方，则称为模的 二次剩余。而一个不是的倍数的数，不同余于任何数的平方，则称为模的 非二次剩余。

对二次剩余求解，也就是对常数解下面的这个方程：

通俗一些，可以认为是求模意义下的开方。这里只讨论 为奇素数 的求解方法，将会使用 Cipolla 算法。

解的数量¶

对于，能满足＂是模的二次剩余＂的一共有个（0 不包括在内），非二次剩余有个。

证明¶

对应了的特殊情况，因此我们只用考虑的情况。

一个显然的性质是，那么当我们可以取到所有解。

接下来我们只需要证明当时两两不同。

运用反证法，假设存在不同的两个整数且，

则有

显然，故假设不成立，原命题成立。

勒让德符号¶

通过勒让德符号可以判断一个数是否为二次剩余，具体判断是否为的二次剩余，需要通过欧拉判别准则来实现。

下表为部分勒让德符号的值

欧拉判别准则¶

若是二次剩余，当且仅当。

若是非二次剩余，当且仅当。

证明¶

由于为奇素数，那么是一个偶数，根据费马小定理，那么就有

其中是一个素数，所以和中必有一个是的倍数，

因此模的余数必然是 1 或者 - 1。

是一个奇素数，所以关于的原根存在。

设是的一个原根，则存在使得。于是就有

是的一个原根，因此模的指数是，于是整除。这说明是一个偶数。

令，就有。是模的二次剩余。

Cipolla 算法¶

找到一个数满足是 非二次剩余，至于为什么要找满足非二次剩余的数，在下文会给出解释。这里通过生成随机数再检验的方法来实现，由于非二次剩余的数量为，接近，所以期望约 2 次就可以找到这个数。

建立一个＂复数域＂，并不是实际意义上的复数域，而是根据复数域的概念建立的一个类似的域。在复数中，这里定义，于是就可以将所有的数表达为的形式，这里的和都是模意义下的数，类似复数中的实部和虚部。

在有了和后可以直接得到答案，的解为。

证明¶

定理 1：

可以发现只有当和时由于没有因子不会因为模被消去，其他的项都因为有因子被消去了。

定理 2：

定理 3：这是费马小定理的另一种表达形式

有了这三条定理之后可以开始推导

参考实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int t;
ll n, p;
ll w;

struct num {  //建立一个复数域
  ll x, y;
};

num mul(num a, num b, ll p) {  //复数乘法
  num ans = {0, 0};
  ans.x = ((a.x * b.x % p + a.y * b.y % p * w % p) % p + p) % p;
  ans.y = ((a.x * b.y % p + a.y * b.x % p) % p + p) % p;
  return ans;
}

ll binpow_real(ll a, ll b, ll p) {  //实部快速幂
  ll ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % p;
    a = a * a % p;
    b >>= 1;
  }
  return ans % p;
}

ll binpow_imag(num a, ll b, ll p) {  //虚部快速幂
  num ans = {1, 0};
  while (b) {
    if (b & 1) ans = mul(ans, a, p);
    a = mul(a, a, p);
    b >>= 1;
  }
  return ans.x % p;
}

ll cipolla(ll n, ll p) {
  n %= p;
  if (p == 2) return n;
  if (binpow_real(n, (p - 1) / 2, p) == p - 1) return -1;
  ll a;
  while (1) {  //生成随机数再检验找到满足非二次剩余的a
    a = rand() % p;
    w = ((a * a % p - n) % p + p) % p;
    if (binpow_real(w, (p - 1) / 2, p) == p - 1) break;
  }
  num x = {a, 1};
  return binpow_imag(x, (p + 1) / 2, p);
}

Tonelli-Shanks 算法¶

大致思路如下：

先令 , 则为奇数。

针对的值分两种情况和进行讨论。

如果：

因为是的二次剩余，所以，即；
由 1 可知，；
注意到，可以得出，进一步得到。

因此时，的值容易求出。

对于的情况，设。

由欧拉判别准则可知，进一步有；
稍作变形得到，即。

所以是模意义下的 1 的次根。

接下来设为模意义下的次单位根。容易发现。

假设我们已经知道：因为，所以有，即；

现在的任务变成了计算。这时候又可以分为两种情况：和。

对于第一种情况，容易得到：，。

对于第二种情况，则有：。我们此时需要找到一个，使得。

寻找的思路如下：因为，所以。

接下来寻找一个非二次剩余：

因为是非二次剩余，所以，即；
稍微变个形得到，即；
。

最后得到。

不断迭代即可得到答案。该做法的时间复杂度约为。

参考实现

import random
# example a, p
a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

b = random.randint(1, p)
while (pow(b, (p-1)//2, p) == 1):
    b = random.randint(1, p)

t = p - 1
s = 0
while (t % 2 == 0):
    s += 1
    t = t // 2
x = pow(a, (t + 1) // 2, p)
e = pow(a, t, p)
k = 1
while (k < s):
    if (pow(e, 1 << (s - k - 1), p) != 1):
        x = x * pow(b, (1 << (k - 1)) * t, p) % p
    e = pow(a, p-2, p) * x % p * x % p
    k += 1
print(x)