二次剩余

· · 个人记录

本文参考 OI-wiki.

下文中，p 将代指任意奇素数。

若不特殊说明，则 $a = b$ 表示 $a$ 和 $b$ 在 $\mathbb{F}_p$ 中相等。即 $a \equiv b \pmod{p}$。 ## 定义：二次剩余 称 $a$ 是 $\bmod p$ 意义下的二次剩余，如果存在 $b \in \mathbb{F}_p

使得 b^2 = a。

一些性质

  1. 在 1, \dots, p-1 中恰有一半，即 \frac{p - 1}{2} 个二次剩余。

    设 g 是 \mathbb{F}_p 的原根，则二次剩余恰为

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

    另一个证明：如果 x^2 \equiv y^2，那么 p|(x+y)(x-y)，所以 x \equiv \pm y. 于是二次剩余恰为 1^2,2^2,\dots,\left(\frac{p-1}{2}\right)^2，并且这些两两不同。

  2. 考虑 $x=g^u,y=g^v$，那么相当于说 $u+v$ 是偶数当且仅当 $u,v$ 都是偶数或者都是奇数。

  3. 令 \left(\frac{a}{p}\right) （Legendre symbol）为：

    0 & a \equiv 0 \\ 1 & a \text{是二次剩余} \\ -1 & a \text{不是二次剩余} \end{cases}

    则 \left(\frac{a}{p}\right) \equiv a^{(p-1) / 2}。

    如果 a = g^u，那么 a^{(p-1) / 2} = g^{u(p-1) / 2}，而这个数等于 \pm1；u 为奇数，即 a 不是二次剩余的时候，a^{(p-1)/2} = -1；否则 a^{(p-1)/2} = 1。

    这样我们还可以得出：

    \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)

  4. 二次互反律：若 q 是另一个奇素数，那么

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

    另外，

    \left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}\quad \left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}

    在 OI 中很少用到，证明比较麻烦，此处略去。

Cipolla 算法

给定 n，我们已经知道如何判断它是否是二次剩余（利用上面的性质 3，只需要做一次快速幂）。现在问题是：如果已知 n 是二次剩余，如何快速求出一个 x 使得 x^2 \equiv n \pmod{p}？

首先我们找到一个 a \in \mathbb{Z}_p 使得 a^2 - n 不是二次剩余。

这一步没有什么高效的办法，可以随机 a。可以证明满足条件的 a 也有 \frac{p-1}{2} 个（见下），所以期望随机 \frac{2p}{p-1} \approx 2 次就可以找到一个满足条件的 a。

不妨设 n \equiv b^2。那么 a^2-b^2=(a+b)(a-b) 不是二次剩余当且仅当 \frac{a+b}{a-b} 不是二次剩余。可以发现 a 在除 b 以外的数（[0,p) 以内）之间遍历一遍的时候 \frac{a+b}{a-b} 在 1 以外的数遍历了一遍。从而恰有 \frac{p-1}{2} 个 a 使得 a^2-b^2 不是二次剩余。

接下来考虑扩域 \mathbb{F}_p[\sqrt{a^2-n}]。（如果 a^2-n 是二次剩余，那这个域就不存在，或者说就等于 \mathbb{F}_p 本身；强行搞出形式的和也会导致得到的结构不是域，从而一些条件不成立）。

也就是所有形如 u + v\sqrt{a^2-n} 的数，其中 u,v\in\mathbb{F}_p。 我们记 \alpha = \sqrt{a^2-n}，那么域中的数即为 u+v\alpha。

在这个扩域中，我们有一些性质：

  1. 这是因为 $(x+y)^p = \sum_{k = 0}^p \binom{p}{k} x^k y^{p-k}$， 而当 $0 < k < p$ 的时候 $\binom{p}{k}$ 被 $p$ 整除。
  2. 因为 $\alpha^p = (a^2-n)^{(p - 1)/2} \alpha = -\alpha$。
  3. 如果 x \in \mathbb{F}_p，那么仍然有 x^p = x。 因为 \mathbb{F}_p 里有 x^p = x，并且嵌入到新的域里面之后乘法法则没有变。

现在令

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

那么

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

于是我们在 \mathbb{F}_p[\sqrt{a^2 - n}] 中求得了 x^2 = n 的一个解。还需要说明 x 一定属于 \mathbb{F}_p。

然而域里面的 k 次方程至多有 k 个解，所以 x^2 = n 至多有两个解。由于 n 是 \mathbb{F}_p 里的二次剩余，所以这两个解都在 \mathbb{F}_p 里。因此这样求得的 x 必定在 \mathbb{F}_p 里。

（类比一下，如果 a > 0 \in \mathbb{R}，x \in \mathbb{C} 使得 x^2 = a，那么一定有 x \in \mathbb{R}）。

在代码实现中，选好 a 之后即可用一个数对 (u,v) 表示 u+v\alpha，乘法规则即为 (u_1,v_1)(u_2,v_2) = (u_1u_2 + (a^2-n)v_1v_2, u_1v_2 + u_2v_1)。

代码实现


typedef long long LL;

int p, l;

struct F2 {
  int u, v;
  F2(int u = 0, int v = 0) : u(u), v(v) {}
  friend F2 operator*(const F2 &a, const F2 &b) {
    LL u = (LL)a.u * b.u + (LL)a.v * b.v % p * l;
    LL v = (LL)a.u * b.v + (LL)a.v * b.u;
   return F2(u % p, v % p);
  }
};

LL pow_mod(LL a, int b) {
    LL ans = 1;
  for (a %= p; b; b >>= 1, a = a * a % p)
    if (b & 1) ans = ans * a % p;
  return (ans + p) % p;
}

F2 pow_mod2(F2 a, int b) {
    F2 ans(1, 0);
  for (; b; b >>= 1, a = a * a)
    if (b & 1) ans = ans * a;
  return ans;
}

LL Cipolla(LL n) {
  LL a = 0;
  while (pow_mod(a * a - n, (p - 1) / 2) != p - 1)
    a = rand() % p;
  l = (a * a - n) % p;
  if (!l) return a;
  return (pow_mod2(F2(a, 1), (p + 1) / 2).u + p) % p;
}