因为有春节,所以实际上寒假比暑假长
主要内容:原根 / 离散对数 / 二次剩余
# 原根
下面只讨论奇素数 $p$ 的原根,在不特别强调时,运算在模 $p$ 意义下进行。
- 前置:阶
对于与 $p$ 互质的常数 $a$,在满足 $a^x\equiv1$ 的所有正整数 $x$ 中,最小的 $x$ 称为 $a$ 模 $p$ 的阶,记作 $ord(a)$。
Theorem 1
当且仅当 $ord(a)\mid x$,有 $a^x\equiv 1$。
证明
假设 $a^x\equiv 1$ 且 $a^y\equiv 1$,则有 $a^{x+y}\equiv 1$ 且 $a^{x-y}\equiv 1$。
辗转相除法可得 $a^{(x,y)}\equiv1$。
$(x,y)\le \min\{x,y\}$,又有 $ord(a)$ 是满足 $a^x\equiv1$ 的最小 $x$,所以 $ord(d)\mid x$。
Theorem 2
若 $k\mid ord(a)$,则 $ord(a^k)=\frac{ord(a)}k$
证明
显然有 $frac{ord(a)}k$ 是 $(a^k)^x\equiv 1$ 的解(代入方程、结合 $ord(a)$ 定义即可证明),只需证明 $\frac{ord(a)}k$ 是最小解。
假如存在 $x_0< \frac{ord(a)}k$ 也是方程的解,则 $kx_0$ 是 $a^x\equiv1$ 的解;而 $kx_0< ord(a)$,与 $ord(a)$ 定义矛盾。
根据 Theorem 1 有推论 $ord(a)\mid (p-1)$,证明即费马小定理。
- 原根
若在模 $p$ 意义下,$x^0,x^1,\cdots,x^{\varphi(p)-1}$ 互不相同,也即 $ord(x)=\varphi(p)$,则称 $x$ 是 $p$ 的原根,记为 $\xi$。
实际上只有形如 $p^k,2p^k$ 的数以及 $2,4$ 有原根(虽然我不会证)。
而根据原根的定义,模 $p$ 意义下的任意元素都可以表示为 $\xi^k$(原根的一个重要作用)。
Theorem 3
设 $\xi$ 是质数 $p$ 的一个原根,则 $\xi^k$ 是原根当且仅当 $(k,p-1)=1$。
由于任意元素都可以用 $\xi^k$ 表示。
假设 $\xi^k$ 是 $p$ 的原根,则必须 $ord(\xi^k)=\varphi(p)=p-1$。令 $h=(k,p-1)$
则有 $ord(\xi^k)\mid\frac{p-1}h$。
- 若 $h\neq 1$,则显然 $\xi^k$ 不是 $p$ 的原根;
- 若 $h=1$,因为 $(\xi^k)^{ord(\xi^k)}\equiv1$,则有 $\xi^{k\cdot ord(\xi^k)}\equiv1$,$p-1\mid ord(\xi^k)$,因此 $ord(\xi^k)=p-1$,也即 $\xi^k$ 是 $p$ 的原根。
根据 Theorem 3,可以知道 $p$ 的原根恰有 $\varphi(p-1)$ 个。
补充一个讲课的dalao不会证所以我也不会证的定理:
Theorem 4(二次互反律)
$p,q$ 均为奇素数,则
$$\left(\frac pq\right)\cdot\left(\frac qp\right)=(-1)^{\frac{p-1}2\times\frac{q-1}2}$$
- 计算原根
直接从小到大枚举 awa
注意到 $p$ 的原根有 $\varphi(p-1)$ 个,其实还是蛮多的,于是枚举不了多少个就可以找到一个最小的原根 $\xi_0$。
然后再枚举 $(k,p-1)=1$ 的 $k$,就可以找出剩下的原根 $\xi_0^k$ 了。(一般不会真的让你求所有原根)
怎么验算数 $x$ 是不是 $p$ 的原根?
- 先验算是否 $ord(x)\mid \varphi(p)$,直接快速幂检验 $x^{\varphi(p)}$ 是否为 $1$ 即可;
- 再验算 $ord(x)$ 是否恰好是 $\varphi(p)$:把 $p-1$ 的所有质因子找出来记为 $P=\{p_1,p_2,\dots,p_m\}$,若 $\forall p_i\in P,x^{\frac{p-1}{p_i}}\not\equiv1$,则 $ord(x)=\varphi(p)$,$x$ 是原根。
- 参考实现
1 | int nprm,nfc,nans; |
# 离散对数
- 引入问题
求出下面方程的所有非负整数解:
其中满足 $(a,p)=1$;亦可扩展至 $(a,p)\neq 1$。
- BSGS(大步小步)
根据欧拉定理,当 $(a,p)=1$ 时,有 $a^{\varphi(p)}\equiv1$。记原方程的最小正整数解为 $x_0$,则原方程的解 $x$ 可以表示为 $x=x_0+k\varphi(p)$,于是只需要求 $x< \varphi(p)$ 的解。
令 $q=\lfloor\sqrt p\rfloor$,将原方程的解 $x$ 分解为 $x=nq-m$,其中 $0\le m< q$。易知 $n$ 的数量级与 $q$ 同阶。
原方程可以写为:
由于 $n,m$ 都是 $O(\sqrt p)$ 级别的,可以先 $O(\sqrt p)$ 将方程一边的所有取值都存进哈希表,然后另一边 $O(\sqrt p)$ 查询哈希表中是否有对应的值。
例如,将 $m=0,1,\cdots,q-1$ 时的全部 $ba^m$ 存入哈希表,然后枚举 $n$,查找哈希表中是否存在 $a^{nq}$。
- exBSGS
之前提到离散对数可以扩展到 $(a,p)\neq 1$ 的情况,下面进行推导。
同余方程 $a^x\equiv b\pmod p$ 有如下性质:
- 记 $(a,p)=g$;
- 若 $g\not\mid b$,则无解,可以从同余方程的本质理解:$a^x=kp+b$,则 $b=a^x-kp$,若有解则 $b$ 必然是 $g$ 的倍数;
- 若 $g\mid b$,则等价为 $\frac{a^x}g\equiv\frac bg\pmod{\frac{p}{g}}$。
于是可以转化为
方程左边相当于带了一个系数,注意到 $a$ 仍有可能和 $\frac pg$ 不互质,只需要一直将方程同除以 $(a,p)$,直到 $a,p$ 互质即可。
记每一次方程整体除的数是 $g_i$,$G=\prod g_i$,最后方程的形式大概是
求解方法还是和 BSGS 一样,用哈希表暴力储存方程一边的所有取值。
注意到我们并不能保证不存在 $x< k$ 的解。在转化过程中我们直接从 $a^x$ 中提取出一个 $a$ 而剩下 $a^{x-1}$ 其实是不严谨的,因为转化时 $a,p$ 不互质,则 $a^{-1}$ 不存在。
于是还要特判一下 $x<k$ 有没有解。
- 参考实现
1 | /* |
# 二次剩余
- 引入问题
求解 $x^2\equiv b\pmod p$,$p$ 是一个奇素数。
若方程有解,则 $b$ 称为 $p$ 的二次剩余
- 勒让德符号
- 一些引理
Lemma 1
$$\left(\frac bp\right)\equiv b^{\frac{p-1}2}$$
简单证明一下:
- 当 $b\equiv0$ 时显然;
- 当 $b$ 是 $p$ 的二次剩余时,$\exists x\in[0,p),x^2\equiv b$;
由费马小定理有 $x^{p-1}\equiv1$,又有 $p$ 是奇素数;
可以写成 $(x^2)^{\frac{p-1}2}\equiv1$,则 $b^{\frac{p-1}2}\equiv1$; - 当 $b$ 不是 $p$ 的二次剩余时,由逆元的唯一性可得 $1,2,\cdots,p-1$ 可以按照“$i$ 和 $b\times i^{-1}$($i$ 的逆元)”的方式刚好划分为 $\frac{p-1}2$ 组,每组乘积为 $b$;
于是把 $1,2,\cdots,p-1$ 全部乘起来就可以得到 $(p-1)!=b^{\frac{p-1}2}$,又有 $(p-1)!\equiv -1$(威尔逊定理,不会 QwQ),则 $b^{\frac{p-1}2}\equiv-1$。
Lemma 2
$p$ 恰好有 $\frac{p-1}2$ 个二次剩余。
证明如下:设 $x,y$ 满足 $x^2\equiv y^2$($x< y$,$x,y\in[1,p-1]$),移项可得:
又有 $p$ 是素数且 $p\not\mid x-y$,则 $(p,x-y)=1$,进而可得 $p\mid x+y$。在 $[1,p-1]$ 中,这样的 $(x,y)$ 与 $x^2\equiv y^2$ 一一对应。
所以 $[1,p-1]$ 中恰有 $\frac{p-1}2$ 个不同的 $x^2$,即 $\frac{p-1}2$ 个二次剩余,剩下的 $\frac{p-1}2$ 个数则是非二次剩余。
于是有结论:$p$ 的二次剩余和非二次剩余一样多。
Lemma 3
$$(a+b)^p\equiv a^p+b^p\pmod p$$
直接二项式展开,$a^ib^{p-i}$ 项的系数为 $C_p^i$。
因为 $p$ 是质数,所以当 $i\neq 0,i\neq p$ 时,$C_p^i=\frac{p!}{i!(p-i)!}$ 的分子是 $p$ 的倍数而分母不是,所以 $p\mid C_p^i$。
取模后只剩下首尾两项。
- Cipolla
如果我们知道 $b$ 是 $p$ 的二次剩余,如何求解?
可以先随机出一个 $a$ 使得 $a^2-b$ 不是 $n$ 的二次剩余,用勒让德函数检验即可。由于 $p$ 的二次剩余和非二次剩余是一样多的,所以可以较快地随机出这个 $a$。
可以知道不存在整数 $x$ 使得 $x^2=a^2-b$,于是我们“扩展数域”,让这样的 $x$ 存在——定义单位 $\omega^2\equiv a^2-b$,类似于复数域,域中的所有数可以表示为 $p+q\omega$ 的形式。
Theorem 5
$(a+\omega)^{\frac{p+1}2}$ 是原方程的一个根。
直接代入证明:
$p$ 是奇素数,$\omega^2\equiv a^2-b$,则
因为 $a^2-b$ 是非二次剩余,所以 $(a^2-b)^{\frac{p-1}2}\equiv-1$。又由费马小定理,$a^p\equiv a$,所以
所以
于是 $x_1=(a+\omega)^{\frac{p-1}2}$。由 Lemma 2,另一个根 $x_2$ 满足 $p\mid x_1+x_2$,则 $x_2\equiv p-x_1$。
因为 $p$ 是奇素数,$x_1,x_2$ 一定奇偶性不同,则有两个不等根。
- 参考实现
> Link 洛谷 P5491
1 | /*Lucky_Glass*/ |
THE END
Thanks for reading!
> Linked 余命3日少女-网易云