省选时的坑:二次剩余

嘛,这又是另一个故事了。

期待系列吧,大概率会有下一期。【嗯,一定是这样。

头图为高斯爷爷的 D.A.

定义

如果整数 $a$ 在模意义下与某个完全平方等价,即存在 $x$ 满足 $x^2 \equiv a\pmod p$,则称 $a$ 是模 $p$ 的二次剩余,否则称为二次非剩余。

记号

高斯曾用 $\mathrm{R}$ 和 $\mathrm{N}$ 表示二次剩余和非剩余,比如
$2\ \mathrm{R}\ 7,5\ \mathrm{N}\ 7$。

一个更常用的记号是勒让德符号
$$
\left(\cfrac{a}{p}\right)=\begin{cases}
0& p \mid a\\
+1& a\ \mathrm{R}\ p,p\nmid a\\
-1& a\ \mathrm{N}\ p,p\nmid a\\
\end{cases}
$$

寻找平方根

当然,模意义下没有平方根。

欧拉准则

令 $p$ 为奇质数,$a$ 与 $p$ 互质,则
$$
a^{\frac{p-1}{2}}\equiv\begin{cases}
1\pmod p & \text{$a$ 是模 $p$ 的二次剩余}\\
-1\pmod p & \text{$a$ 是模 $p$ 的二次非剩余}
\end{cases}
$$

证明

由于 $p$ 是一个奇质数,由费马小定理,有
$$
\begin{align*}
a^{p-1}&\equiv 1\pmod p\\
(a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)&\equiv 0\pmod p
\end{align*}
$$
,若 $a$ 是二次剩余,则 $\exists x,x^2\equiv a\pmod p$,有
$$
a^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1\pmod p
$$
,所以所有奇质数的非零二次剩余会使 $a^{\frac{p-1}{2}}\equiv 1\pmod p$,因此所有奇质数的二次非剩余会使 $a^{\frac{p+1}{2}}\equiv 1\pmod p$。

显然它和勒让德符号等价。

奇质数

问题描述

$x^2\equiv a\pmod p$,已知 $a,p$,求 $x$。

题解

  1. 随机生成一个数 $b$ 使得 $b^2-a$ 是二次非剩余。
  2. $x=\pm \left(b+\sqrt{b^2-a}\right)^{\frac{p+1}{2}}$。
    时间复杂度 $\mathcal O(\log p)$

证明

首先第一步的时间复杂度是 $\mathcal O(\log p)$,为什么呢?这涉及到二次剩余的一个性质:$[1,p-1]$ 中的二次剩余有 $\cfrac{p-1}{2}$ 个。

显然,$a^2$ 和 $(p-a)^2$ 是等价的。

目前最优的方法是随机生成一个数然后使用欧拉准则判断。

但为什么寻找 $b$ 是 $\mathcal O(1)$ 的呢?

考虑问题的本质,$b$ 有多少个?答案是有 $\cfrac{p-1}{2}$ 个 $b$ 满足条件。

使用反证法,即证明有 $\cfrac{p-1}{2}$ 个 $b$ 会使 $b^2-a$ 是二次剩余,即满足
$$
\begin{align*}
b^2-a &\equiv s^2 \pmod p\\
(b+s)(b-s) &\equiv a \pmod p
\end{align*}
$$
,的 $b$ 有 $\cfrac{p-1}{2}$ 个。设 $t\in[1,p-1]$,有
$$
\begin{cases}
b+s\equiv t\pmod p\\
b-s\equiv\cfrac{a}{t}\pmod p
\end{cases}
$$
若对不相等的 $t,t’$,$b$ 相等的话,有
$$
b\equiv\cfrac{t+\cfrac{a}{t}}{2}\equiv\cfrac{t’+\cfrac{a}{t’}}{2}\pmod p\\
tt’\equiv a\pmod p
$$
,于 $\forall t$,总能找到 $t’=\cfrac{a}{t}$,除了 $x$ 和 $-x$ 配对,所以不相等的 $b$ 有 $\cfrac{p-1-2}{2}+1=\cfrac{p-1}{2}$ 个。

那么就会有 $p-1-\cfrac{p-1}{2}=\cfrac{p-1}{2}$ 个 $b$ 满足条件咯。

但是第二步。。。这个是不是自相矛盾了?不是才说了 $b^2-a$ 是二次非剩余吗,怎么还开根了?

【我也不知道,正在询问毕姥爷和 zsh。。。

询问结束,我只能口胡了。

嘛我们先介绍另一个概念。

域是一个集合,有两个二元运算符 $+,\cdot$(加和乘),并且满足以下规则,被称为域公理。

  1. 封闭性
  2. 结合律
  3. 交换律
  4. 加法单位元,称作 $0$
  5. 乘法单位元,称作 $1$
  6. 加法逆元
  7. 非 $0$ 元素乘法逆元
  8. 乘法分配律

可以说一个域有加法和乘法,在加法下是一个阿贝尔群,单位元是 $0$;非零元素构成一个乘法下的阿贝尔群,并且满足乘法分配律。

域扩展

如果域 $F$ 是域 $E$ 的子集,并且 $F$ 的运算符对 $E$ 都适用,则称 $E$ 是 $F$ 的扩展域。这样的一对域叫做域扩展,记作 $E/F$。

域扩展度

如果 $E/F$ 是一个域扩展,那么 $E$ 可以认为是一个在 $F$ 上的向量空间,这个向量空间的维数叫做域扩展度。

数域

一个数域是一个有限度数的扩展实数域。

证明(续)

所以说这个解法在这里定义了一个二维数域,集合为 $\{(x,y)\mid x,y\in\mathbb{Z},0\le x,y\le p\}$,运算符为
$$
(x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2)\\
(x_1,y_1)\cdot (x_2,y_2)=(x_1x_2+y_1y_2w,x_1y_2+y_1x_2)
$$
其中 $w=b^2-a$,所以有
$$
加法单位元:(x,y)+(-x,-y)=(0,0)\\
乘法单位元:(x,y)\cdot \left(\cfrac{x}{x^2-y^2w},-y\right)=(1,0)
$$
,这些运算都是在模 $p$ 意义下进行的。

现在来证明 $x=\pm \left(b+\sqrt{b^2-a}\right)^{\frac{p+1}{2}}$。

$
设 c=\sqrt{b^2-a}\\
x^2=(b+c)^{p+1}\\
\because c^2 是二次非剩余\\
\therefore c^{2\cdot \frac{p-1}{2}}\equiv c^{p-1}\equiv -1\pmod p\\
\because (x+y)^p\equiv x^p+y^p\pmod p\\
\therefore x^2\begin{align*}
&\equiv (b^p+c^p)(b+c)\\
&\equiv (b-c)(b+c)\\
&\equiv b^2-c^2\equiv b^2-b^2+a\equiv a\pmod p
\end{align*}
$

完成了。

一些想法

可以发现这个数域和复数域很类似,要是我们稍稍改一下能不能把它改成复数域呢?

我不知道诶,坑。

奇质数的幂

2 的幂

坑。

参考二次剩余及计算方法。【Miskcoo tql!

合数

CRT【手动滑稽。

是不是全天下的合数都是 CRT 解决的啊。。。