题解 P5491 【【模板】二次剩余】

hly1204 · 2020-09-10 06:36:41 · 题解

重新写了一下，补充了一些东西。。

元素的阶

定义：在模正整数 m 意义下，对于一个正整数 x 与 m 互素，我们说 x 的阶为 t ，记作 \operatorname{ord}_{m}(x)=t ，其中 t 为满足 x^{t}\equiv 1\pmod{m} 的最小正整数。

当模数明确时，也简记为 \operatorname{ord}(x) ，而当 x 与 m 不互素时，则为未定义。

下面在模正整数 m 意义下，且 \gcd(x,m)=1 ，考虑 \operatorname{ord}(x)=t ，有

且对于某个正整数 k 存在

显然 k\operatorname{ord}(x^{k})\geq t 且

又因为

我们有

综上，有 \displaystyle \operatorname{ord}(x^{k})=\frac{\operatorname{ord}(x)}{\gcd(\operatorname{ord}(x),k)} 。

当模数 m 为奇素数时，原根 g 的阶为 m-1 。

欧拉准则

Euler's criterion ： 设 p 为奇素数， n 为正整数， \gcd(a,p)=1 ，则 a 是一个 n 次剩余当且仅当 a^{(p-1)/\delta}\equiv 1\pmod{p} ，其中 \delta =\gcd(p-1,n) 。

这里只需考虑 n=2 时的情况。

根据费马小定理，有 p 为奇素数且 \gcd(a,p)=1 时，有 a^{p-1}\equiv 1\pmod{p} ，那么显然可以得知 a^{(p-1)/2}\equiv \pm 1\pmod{p} ，根据欧拉准则即可判断是否为二次剩余（ quadratic residue ）。

若不满足欧拉准则，这里称为二次非剩余（ quadratic non-residue ）。

Tonelli-Shanks 算法

设 p 为奇素数，求关于 x 的同余方程 x^{2}\equiv a\pmod{p} 的解（不考虑 a\equiv 0\pmod{p} 的情况）。

使用欧拉准则判断方程是否有解，若有解，则 a^{\frac{p-1}{2}}\equiv 1\pmod{p} 否则 a^{\frac{p-1}{2}}\equiv -1\pmod{p} 。

下面仅考虑有解的情况。

特殊情况：若 p\bmod{4}=3 那么有

那么 a^{\frac{p+1}{4}} 为一个解。

找到某些 r,s 满足 2^{r}\cdot s=p-1 且 s 为奇数，在 \mathbb{Z}\cap [1,p-1] 中用随机方法寻找一个二次非剩余 v ，可以认为存在某个原根 g^{k}\equiv v\pmod{p} 且 k 为奇数，那么对于 \displaystyle \operatorname{ord}(v^{s})=\operatorname{ord}(g^{sk})=\frac{2^{r}\cdot s}{\gcd(2^{r}\cdot s,sk)}=2^{r} ，令 x_{0}=a^{\frac{s+1}{2}}\bmod{p},w=v^{s}\bmod{p} ，显然 v^{s} 的阶为 2^{r} ，对于 x_{0} ，有

令 \displaystyle 2^{t_{0}}=\operatorname{ord}\left(\frac{x_{0}^{2}}{a}\right) （这里显然可以发现 x_{0}^{2}/a=a^{s} 的阶是二的幂次），且设

注意到 \displaystyle \operatorname{ord}\left(\frac{x_{i}^{2}}{a}\right)=2^{t_{i}}\implies\left(\frac{x_{i}^{2}}{a}\right)^{2^{t_{i}-1}}\equiv -1\pmod{p} ，同样的 \operatorname{ord}(w)=2^{r}\implies w^{2^{r-1}}\equiv -1\pmod{p} ，那么

显然可以发现 t_{i+1}\lt t_{i} ，而 t_{0}\lt r\lt \log_{2}(p) ，那么 t_{0} 可枚举计算，而 t_{i} 每一次至少减少 1 最多减少 \log_{2}(p) 次，那么该算法为多项式时间，当 t_{n}=0 时有 x_{n}^{2}\equiv a\pmod{p} 得到了一个解。

这个算法让我注意到一般对于模素数 p 的数论变换中寻找原根是不必要的，只需要随机寻找一个二次非剩余计算阶为 2 幂次的数，即可生成所需要的“单位根”。

补充

参考 [2] 的 p101 我们可以得到另一种特殊的情况（很感激滑铁卢大学对文献的开源）：

当奇素数 p\equiv 5\pmod{8} 且 a 为一个二次剩余时，令 d\equiv a^{(p-1)/4}\pmod{p} ，有 r 满足 r^{2}\equiv a\pmod{p}

但关于这个的证明我也没有尝试。

对于每个元素 a\in\mathbb{F}_{2^{m}} 都有一个模平方根为 a^{2^{m-1}} 。

实装

#include <random>

typedef unsigned int uint;

uint pow_mod(uint x, uint y, uint p) { // 计算 x^y mod p，设 y 大于等于 0
  uint res = 1;
  for (; y != 0; y >>= 1, x = static_cast<long long>(x) * x % p)
    if ((y & 1) != 0) res = static_cast<long long>(res) * x % p;
  return res;
}

uint tonelli_shanks(uint x, const uint p) { // 假设 p 为奇素数，计算 x^{1/2}
  if (x <= 1) return x;
  if (pow_mod(x, p >> 1, p) != 1) return 0; // p >> 1 即 (p - 1) / 2 ，欧拉准则判断
  if ((p & 3) == 3) return pow_mod(x, p + 1 >> 2, p); // 特殊情况，p mod 4 = 3
  uint r = 0, s = p - 1;                              // 2^r * s = p - 1
  while ((s & 1) == 0) ++r, s >>= 1;

  static std::random_device rd;
  static std::mt19937 gen(rd());
  std::uniform_int_distribution<uint> dis(2, p - 1);

  uint v; // 随机找一个 v 为二次非剩余
  for (; pow_mod(v = dis(gen), p >> 1, p) == 1;) {
  }

  uint w = pow_mod(v, s, p); // w = v^s

  uint t = 0;
  uint ix = pow_mod(x, p - 2, p);                      // ix = x^{-1}
  x = pow_mod(x, s + 1 >> 1, p);                       // x = x^{(s+1)/2}
  uint y = static_cast<long long>(x) * x % p * ix % p; // y = x^s
  for (; pow_mod(y, 1 << t, p) != 1; ++t) {            // 2^t = ord(x^s) ，计算 t0
  }
  while (t != 0) {
    x = static_cast<long long>(x) * pow_mod(w, 1 << r - t - 1, p) % p;
    y = static_cast<long long>(x) * x % p * ix % p;
    for (--t; t != 0 && pow_mod(y, 1 << t - 1, p) == 1; --t) {
    }
  }
  return x;
}

参考文献

[1] Jeremy Booher. Square Roots in Finite Fields and Quadratic Nonresidues

[2] A. Menezes, P. van Oorschot and S. Vanstone. Handbook of Applied Cryptography, 1996.