Sweetlemon 的博客

Sweetlemon 的博客

关于二次剩余——开根号的神奇操作

posted on 2020-07-23 22:47:28 | under 算法浅解 |

很久以前看《数论入门》这本书的时候就听说了二次剩余,后来看《数论概论》的时候认真学习了一番,这回终于学会了程序实现。

下面简单介绍二次剩余的相关定理、算法等。

一些定义

什么叫二次剩余呢?我们经常在实数集上做“开方”运算,简单地说就是求解方程 $x^2=a$。那么我们能不能在模意义下开方呢?也就是,能否解方程 $x^2\equiv a\pmod{p}$?

为了方便,我们只讨论 $p$ 是质数的情形;而 $p=2$ 的情形稍有特殊,而且也很平凡,因此我们不讨论 $p=2$。简而言之,本文中 $p$ 是奇质数。

我们来看一些平方表。下表中的数字依次是 $1,2,3,\cdots,p-1$ 的平方。

$x^2\equiv 1,1 \pmod{3}$

$x^2\equiv 1,-1,-1,1 \pmod{5}$

$x^2\equiv 1,-3,2,2,-3,1 \pmod{7}$

$x^2\equiv 1,4,-2,5,3,3,5,-2,4,1\pmod{11}$

$x^2\equiv 1,4,-4,3,-1,-3,-3,-1,3,-4,4,1\pmod{13}$

$x^2\equiv 1,4,-8,-1,8,2,-2,-4,-4,-2,2,8,-1,-8,4,1\pmod{17}$

$x^2\equiv 1,4,9,-3,6,-2,-8,7,5,5,7,-8,-2,6,-3,9,4,1\pmod{19}$

$x^2\equiv 1,4,9,-7,2,-10,3,-5,-11,8,6,6,8,-11,-5,3,-10,2,-7,9,4,1\pmod{23}$

$x^2\equiv 1,4,9,-13,-4,7,-9,6,-6,13,5,-1,-5,-7,-7,-5,-1,5,13,-6,6,-9,7,-4,-13,9,4,1\pmod{29}$

观察这些表可以发现,平方表是回文的。这个很容易理解,因为 $x^2\equiv (p-x)^2\pmod{p}$。

并且,我们发现,这张表中,每个数恰出现两次。会出现至少两次的原因在上一段已经解释了,那么为什么是两次呢?也就是,为什么模 $p$ 的缩系(记为 $M_p$)恰好有两个数的平方相等呢?

假设 $\{a,b\}\sube M_p$(这隐含了 $a,b$ 模 $p$ 不同余),并且 $a^2\equiv b^2$。移项并因式分解得到 $(a+b)(a-b)\equiv 0$。由于 $a,b$ 不同余,因此 $a+b\equiv 0$ 一定成立,这就说明,两个不同余的数模 $p$ 平方相同,当且仅当他们的和是 $p$ 的倍数。这样就解释了两次。

还有另一个角度可以解释。由多项式拉格朗日定理知, $x^2\equiv a$ 这个二次方程至多有两个解;而只要这个数在表中出现了,那么就会出现两次。

由平方表中每个数恰出现两次知,平方表中共有 $\cfrac{p-1}{2}$ 种不同的数。那么我们可以进行以下定义:

若 $\exists x\in M_p,x^2\equiv a$,则称 $a$ 是 $\bmod p$ 的二次剩余。在 $M_p$ 中但不是二次剩余的数称为 $\bmod{p}$ 的二次非剩余

注意这个定义和“电解质”、“非电解质”的定义有一点点类似:电解质和非电解质只讨论化合物, $\mathrm{Cl}_2$ 不是电解质也不是非电解质;二次剩余和二次非剩余只讨论缩系, $0$ 不是二次剩余也不是二次非剩余。

勒让德提出了一个简单的符号(但是 $\LaTeX$ 打起来很麻烦)来表示一个数是不是 $\bmod{p}$ 的二次剩余。 $\left(\cfrac{a}{p}\right)=1$ 表示 $a$ 是 $\bmod{p}$ 的二次剩余, $\left(\cfrac{a}{p}\right)=-1$ 表示 $a$ 是 $\bmod{p}$ 的二次非剩余, $\left(\cfrac{a}{p}\right)=0$ 表示 $a$ 既不是 $\bmod{p}$ 的二次剩余也不是二次非剩余(这说明 $a\equiv 0\pmod{p}$)。这被称为勒让德符号。

二次剩余的判定:欧拉准则

如何判断一个数是不是二次剩余呢?最简单也最暴力的方法就是直接枚举 $M_p$ 中的数计算平方,这样还能同时计算出这个数的“平方根”。复杂度是 $\mathrm{O}(n)$ ,通常可以用于本地处理。

事实上,勒让德符号是可以“计算”的!对,就是计算。

回忆费马小定理: $\forall a\in M_p,a^{p-1}\equiv 1$。那 $a^{\frac{p-1}{2}}$ 是多少呢?

设 $b\equiv a^{\frac{p-1}{2}}$,那么 $b^2\equiv 1$。根据上面的讨论,我们知道, $b$ 要么是 $1$,要么就是 $-1$。事实上, $b$ 就等于 $\left(\cfrac{a}{p}\right)$。

我们用一个简单的办法证明。因为 $p$ 是奇质数,因此 $p$ 存在原根,取其一个原根 $g$。设 $a\equiv g^c$,那么 $a$ 是二次剩余当且仅当 $c$ 是偶数。如果 $c$ 是偶数,那么设 $c=2k\ (k\in \mathbb{N})$,则 $b\equiv a^{\frac{p-1}{2}}\equiv g^{c\cdot \frac{p-1}{2}}\equiv g^{k(p-1)}\equiv\left(g^{p-1}\right)^k\equiv 1$。反之,如果 $c$ 是奇数,设 $c=2k+1\ (k\in \mathbb{N})$,则 $b\equiv a^{\frac{p-1}{2}}\equiv g^{c\cdot \frac{p-1}{2}}\equiv g^{k(p-1)+\frac{p-1}{2}}\equiv g^{\frac{p-1}{2}}$。考虑 $-1$ 在原根 $g$ 下的指标 $t$ ,因为 $(-1)^2\equiv 1$,因此 $2t\equiv 0\pmod{p-1}$,知 $t$ 是 $\cfrac{p-1}{2}$ 的倍数;但 $t$ 不能是 $0$( $1$ 的指标是 $0$),因此 $t=\cfrac{p-1}{2}$。于是 $c$ 是奇数时, $b\equiv g^{\frac{p-1}{2}}\equiv -1$。

由此,我们(基本)证明了 $\left(\cfrac{a}{p}\right)=a^{\frac{p-1}{2}}$,这被称为欧拉准则。(事实上还要对 $a\equiv 0$ 的情况稍加讨论)

在 OI 中,要计算勒让德符号的值,欧拉准则已经基本够用;下面要介绍的二次互反律,是另一种计算勒让德符号的值,当然在 OI 中可能没有太大的意义。

二次剩余的判定:二次互反律

欧拉准则计算勒让德符号时需要乘方,这对手算十分不友好。“二次互反律”这种计算方法类似与辗转相除,更便于手算。

这个定理的证明比较繁琐,我不打算在这里证明,可以看这篇回答

这个定理的结论是,对不同的奇质数 $p,q$, $\left(\cfrac{p}{q}\right)\left(\cfrac{q}{p}\right)=(-1)^{\frac{(p-1)}{2}\frac{(q-1)}{2}}$。也就是,当且仅当 $p,q$ 均为 $4k+3$ 型质数时, $\left(\cfrac{p}{q}\right)$ 和 $\left(\cfrac{q}{p}\right)$ 不同。

利用二次互反律和另外几个结论,我们可以用另外一种方法计算勒让德符号。

我们先叙述这几个额外的结论。

  1. $\left(\cfrac{a}{p}\right)=\left(\cfrac{a\% p}{p}\right)$。非常简单,根据定义就可得。
  2. $\left(\cfrac{a^2}{p}\right)=1$。根据定义可得。
  3. $\left(\cfrac{ab}{p}\right)=\left(\cfrac{a}{p}\right)\left(\cfrac{b}{p}\right)$(完全积性)。根据欧拉准则得证。
  4. $\left(\cfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$,也即当且仅当 $p\equiv \pm 1\pmod{8}$ 时, $2$ 是 $\bmod{p}$ 的二次剩余。这个结论需要用高斯引理证明,这里不进行过多叙述。

利用这几个结论,我们就能够用类似辗转相除的方法求勒让德符号了。

用这种方法计算 $\left(\cfrac{a}{p}\right)$ 的步骤如下:

  1. 将 $a$ 分解质因数,并把每个质因数的次数模 $2$。假设 $a$ 的指数为奇数的质因数有 $q_1,q_2,\cdots,q_k$ 这 $k$ 个,那么 $\left(\cfrac{a}{p}\right)=\left(\cfrac{q_1}{p}\right)\left(\cfrac{q_2}{p}\right)\cdots \left(\cfrac{q_k}{p}\right)$ ,分别递归计算。这一步的依据是第 2, 3 条结论。
  2. 经过第一步后,只需计算一个质数 $q$ 的 $\left(\cfrac{q}{p}\right)$ 的值。讨论 $q$。
    1. 如果 $q=2$,那么根据第 4 条结论直接返回值。
    2. 如果 $q=p$,返回 $0$。
    3. 如果 $q>p$,那么将 $q$ 模 $p$,返回上面的第 $1$ 步(分解质因数等)。
    4. 如果 $q<p$,那么用二次互反律调整成 $q>p$ 的情形。

举个例子,计算 $\left(\cfrac{360}{2333}\right)$。 $$ \begin{aligned} &\left(\cfrac{360}{2333}\right)\\ =&\left(\cfrac{2^3\times3^2\times 5}{2333}\right)\\ =&\left(\cfrac{2}{2333}\right)\times\left(\cfrac{5}{2333}\right)\\ =&-\left(\cfrac{5}{2333}\right)\\ =&-\left(\cfrac{2333}{5}\right)\\ =&-\left(\cfrac{3}{5}\right)\\ =&-\left(\cfrac{5}{3}\right)\\ =&-\left(\cfrac{2}{3}\right)\\ =&1 \end{aligned} $$ 第一步是分解质因数,第二步是根据第 2,3 条结论把一个勒让德符号拆开,第三步是根据第 4 条结论计算,第四步运用二次互反律,第五步利用第 1 条结论取模,第六步运用二次互反律,第七步利用第 1 条结论取模,最后一步根据第 4 条结论计算出答案。

这个过程最为棘手的是分解质因数,这个并不太高效,所以这个算法对 OI 来说价值不是那么大。

二次剩余的计算:Cipolla 算法

前面一段都是“没用的”,现在来讲一点对 OI 有用的:如何计算 $x^2\equiv a\pmod{p}$ 的解?

尽管 $a$ 是 $\bmod{p}$ 的二次剩余,但在计算上述 $x$ 的过程中,可能会用到一些 $M_p$ 以外的数;就像求解有三个实根的三次方程的过程中仍有可能出现虚数一样。

求解二次剩余的 Cipolla 算法就用到了这样的扩域思想,求解的过程中要用到所谓的“虚数”。

我们首先在 $[0,p)$ 中随机取一个整数 $b$,使得 $b^2-a$ 是 $\bmod{p}$ 的二次非剩余。这一步看上去非常奇怪,但这是为扩域做准备。这一步是否一定能做到呢?也就是,是否有可能无论取什么 $b$,都会让 $b^2-a$ 不是二次非剩余呢?

因为 $a$ 是 $M_p$ 中的元素,我们可以设 $b^2=1-ka$( $k=(1-b^2)a^{-1}$ 一定存在)。把所有二次剩余的 $k$ 排起来,这些 $k$ 一共只有 $\cfrac{p-1}{2}$ 个,而 $k$ 的取值范围是 $[0,p)$,所以一定存在一个 $b^2$,使得它减 $a$ 得到的数是二次非剩余。至于这样的 $b^2$ 有多少个,就不是那么容易得到;但期望意义下,不用随机太多的次数就能得到一个合法的 $b$。

我们设 $\omega^2=b^2-a$,注意这里 $\omega^2$ 是 $M_p$ 的一个元素(是一个二次非剩余),而 $\omega$ 本身并不存在于 $M_p$ 中,是一个“虚数”。而接下来的算法中要用到的数,就表示成 $c+d\omega$ 的样子,这和 $a+b\mathrm{i}$, $2+\sqrt{3}$ 差不多,在运算时都要分别处理。很自然地, $(x+y\omega)(u+v\omega)=(xu+yv\omega^2)+(xv+yu)\omega$。

接下来,我们说明几个性质。

  • $(x+y)^p\equiv x^p+y^p\pmod{p}$。用二项式定理展开,得到 $(x+y)^p=\sum_{i=0}^p\mathrm{C}_p^ix^i y^{p-i}$,而由卢卡斯定理(或者简单讨论一下)可知,只有 $i=0$ 或 $i=p$ 时 $\mathrm{C}_p^i$ 不是 $p$ 的倍数,因此这个性质得证。
  • $\forall x\in \mathbb{Z},x^p\equiv x\pmod{p}$。这个是费马小定理的直接推论,并且适用于任何整数,包括 $0$。
  • $\omega^p\equiv -\omega$。 $\omega^{p}=(\omega^2)^{\frac{p-1}{2}}\omega\equiv -\omega$,最后一步是因为 $\omega^2$ 是 $\bmod{p}$ 的二次非剩余。

根据这几个性质,我们可以证明, $x=(b+\omega)^{\frac{p+1}{2}}$ 就是 $x^2\equiv a\pmod{p}$ 的解!

为什么呢?我们来推导。 $$ \begin{aligned} &x^2\\ =&(b+\omega)^{p+1}\\ =&(b+\omega)^p(b+\omega)\\ \equiv &(b^p+\omega^p)(b+\omega)\\ \equiv&(b-\omega)(b+\omega)\\ =&b^2-\omega^2\\ =&b^2-b^2+a\\ =&a \end{aligned} $$ 其中第一步代入 $x$ 的定义,第二步拆开以出现 $p$ 次方,第三步运用性质 1,第四步运用 $b^p\equiv b$ 和 $\omega^p\equiv -\omega$,接下来就是简单的化简了。经过这样的推导,我们就证明了这个 $x$ 是 $x^2\equiv a$ 的一个解;另一个解自然就是 $-x$ 了。

且慢!万一 $x$ 里面含有 $\omega$ 项怎么办?我们尝试用反证法说明这不可能成立。

假设 $x=u+v\omega\ (v\neq 0)$,那么 $x^2=u^2+2uv\omega +v^2\omega^2=(u^2+v^2\omega^2)+2uv\omega$。由于 $x^2\equiv a$ 不带 $\omega$ 项,因此 $2uv\equiv 0$;由于 $v\neq 0$,知 $u\equiv 0$(注意 $p$ 是奇质数)。这样 $x^2=v^2\omega ^2$。两边同乘 $v$ 的逆元(因为 $v$ 非零,所以逆元存在),得到 $\omega^2=(xv^{-1})^2$,从而 $\omega^2$ 不是二次非剩余,矛盾。

因此, $x$ 中一定不含 $\omega$ 项;也就是说,这么解出来的 $x$ 就是我们想要求的。

这个算法的主要瓶颈在于求 $(b+\omega)^{\frac{p+1}{2}}$ 需要快速幂,因此时间复杂度 $\mathrm{O}(\log p)$,比较优秀。

关于这个算法的记忆,我建议可以记下 $x=(b+\omega)^{\frac{p+1}{2}}$,然后从结果 $x^2=b^2-\omega^2$ 推出 $\omega^2=b^2-a$。

二次剩余可以直接在计算中应用,比如假设 $x^2\equiv 5\pmod{p}$,那么可以用 $x$ 代替 $\sqrt{5}$,比如 $\cfrac{\sqrt{5}+1}{2}\equiv \cfrac{x+1}{2}$,这样最后的运算结果模 $p$ 还是正确的。

二次非剩余?不怕

我们知道, $5$ 是 $\bmod{10^9+9}$ 的二次剩余,但是 $\bmod{10^9+7}$ 下的二次非剩余。如果想要在 $\bmod{10^9+7}$ 下运用斐波那契数列的通项公式 $F_n=\cfrac{1}{\sqrt{5}}\left(\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\left(\cfrac{1-\sqrt{5}}{2}\right)^n\right)$ 进行计算,是不是就没有办法了呢?

受到上面算法的启发,我们是不是可以像上面那样,令 $\omega^2=5$,用“虚数”的形式来表示 $\sqrt{5}$ 呢?答案当然是肯定的。程序实现和上面类似,可能要额外实现复数的加法和减法。

事实上,这个方法被成为“扩域”,在神鱼的这篇题解里有一些介绍。如果题目中只有一个二次非剩余,那这种方法无疑是比较好用的;如果题目中有好几个二次非剩余,那虚数的计算就会变得十分繁琐(做过毒瘤数学题的都懂)。

那么这篇关于二次剩余的总结就到此结束了,希望能有所收获。