原根

在(a,m)=1时，定义a对模m的指数$\delta m(a)$为使$a^d \equiv 1 \pmod{m}$成立的最小的正整数d

若$\delta m(a)=\varphi(m)$，则称a是模m的原根

模$m$有原根的充要条件是$m = 2 , 4 , p^n , 2p^n$，其中$p$是奇素数，$n$是任意正整数。

原根定理

素数p的原根个数为$\varphi(p-1)$

指标

当确定模p和原根g时，定义a的指标为$I(a)$为使$g^d \equiv a \pmod p$成立的最小的正整数d

指标法则

① $$I(ab) \equiv I(a)+I(b) \pmod {p-1}$$

② $$I(a^k) \equiv kI(a) \pmod {p-1}$$

求原根

从小到大枚举数$g$判断其是不是原根

对于一个待检查的$g$，检查下面式子是否成立

$$g^{(p-1)/a} \equiv 1 \pmod p$$

若成立则g不为原根（其中a为p-1的质因子）

求所有原根

若已求得一个模p意义下的原根g，则所有原根为

$$g^k \quad (gcd(k,p-1)=1)$$

二次剩余

与一个平方数模$p$同余的非零数为模$p$的二次剩余，与任意平方数模$p$都不同余的非零数为模$p$的非二次剩余

对于奇素数p，各有$\frac {p-1}{2}$个二次剩余和非二次剩余

勒让德符号

$$\left(\frac{a}{p}\right) = \begin{cases} +1 \\ -1 \end{cases}$$

二次互反率

设$p,q$为不同的奇素数，则

$$\left(\frac{-1}{p}\right)=\begin{cases} +1 \quad 如果p \equiv 1 \pmod 4 \\ -1 \quad 如果p \equiv 3 \pmod 4\end{cases}$$

$$\left(\frac{2}{p}\right)=\begin{cases} +1 \quad 如果p \equiv 1或7 \pmod 8 \\ -1 \quad 如果p \equiv 3或5 \pmod 8\end{cases}$$

$$\left(\frac{q}{p}\right)=\begin{cases} +\left(\frac{p}{q}\right) \quad 如果p \equiv 1 \pmod 4或q \equiv 1 \pmod 4\\ -\left(\frac{p}{q}\right)  \quad 如果p \equiv q \equiv 3 \pmod 4\end{cases}$$

广义二次互反律

设$p,q$为正奇数，则

$$\left(\frac{-1}{b}\right)=\begin{cases} +1 \quad 如果b \equiv 1 \pmod 4 \\ -1 \quad 如果b \equiv 3 \pmod 4\end{cases}$$

$$\left(\frac{2}{b}\right)=\begin{cases} +1 \quad 如果b \equiv 1或7 \pmod 8 \\ -1 \quad 如果b \equiv 3或5 \pmod 8\end{cases}$$

$$\left(\frac{a}{b}\right)=\begin{cases} +\left(\frac{b}{a}\right) \quad 如果a \equiv 1 \pmod 4或b \equiv 1 \pmod 4\\ -\left(\frac{b}{a}\right)  \quad 如果a \equiv b \equiv 3 \pmod 4\end{cases}$$

二次剩余求解

求$x^2 \equiv a \pmod p$最小非负整数解，其中p为素数

①

当p为2时，$x=a \mod p$

②

当p为奇素数时

由欧拉准则可知，$a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \pmod p$

当$a^{(p-1)/2} \equiv -1 \pmod p$时无解；

当$a^{(p-1)/2} \equiv 1 \pmod p$且$p \equiv 3 \pmod 4$时，$x=a^{(n+1)/4}$；

当$a^{(p-1)/2} \equiv 1 \pmod p$且$p \equiv 1 \pmod 4$时：

设 $$b^{(p-1)/2} \equiv -1 \pmod p ~,~ i=(n-1)/2 ~,~ k=0$$

所以 $$a^ib^k \equiv 1 \pmod p$$

若$i \mod 2=0$，则$i,k$同时取半，此时$a^ib^k \equiv \pm1 \pmod p$

若$a^ib^k \equiv -1 \pmod p$，则$k=k+(n-1)/2$

不断递归下去，直到$i \mod 2=1$

最后$x=a^{(i+1)/2}b^{k/2}$

离散对数（BSGS算法）

解$a^x \equiv b \pmod p$的最小整数解，其中p为素数

解法：BSGS算法

设s是满足$s*s>p$的最小整数

先预处理出$x^i(i \in [0,s-1])$并用Hash表储存

然后枚举$x^{is}(i \in [0,s-1])$，通过乘法逆元求出满足$c*x^{is}\equiv n(mod\;p)$的c，再判断c是否位于Hash表内，从而找到解

离散对数（ExBSGS算法）

解$a^x \equiv b \pmod m$的最小整数解

首先在$[0,log(m)]$的范围内暴力枚举x

不妨令$d=gcd(a,m)$，若d=1则直接套用BSGS，若$b \mod d \not= 0$则无解

其余情况我们则将原式两边同除$d$

$$a^x \equiv b \pmod m ~\Rightarrow~ \frac ad*a^{x-1} \equiv \frac bd \pmod {\frac md}$$

继续重复，直到$d=gcd(a,\frac m{d_1d_2...})=1$

此时原式

$$\frac {a^k}{d_1d_2...}*a^{x-k} \equiv \frac {b}{d_1d_2...} \pmod {\frac {m}{d_1d_2...}}$$

$$a^{x-k} \equiv \frac {b}{d_1d_2...}*(\frac {a^k}{d_1d_2...})^{-1} \pmod {\frac {m}{d_1d_2...}}$$

接下来就求逆元完套BSGS

N次剩余求任意解

求$x^k \equiv b \pmod m$任意解，其中$gcd(b,m)=gcd(k,\varphi(m))=1$

设数$u$满足

$$ku \equiv 1 \pmod {\varphi(m)}$$

则解为

$$x=b^u \pmod m$$

证明：

$$\begin{align} x^k &= (b^u)^k \\ &= b^{uk} \\ &= b^{1+\varphi(m)v} \\ &= b \cdot (b^{\varphi(m)})^v \\ & \equiv b \pmod m \end{align}$$

N次剩余求所有解

求$x^k \equiv b \pmod p$所有解

设$g$为原根，令$g^y=x ~,~g^t=b$，则有 $$g^{yk} \equiv g^t \pmod p ~\Rightarrow~ yk \equiv t \pmod {p-1}$$

求原根g完，t用离散对数求，y用Exgcd求，x用快速幂求

询问某数是否为两平方数之和

①素数$p$能表示成两平方数之和

条件：

$$p是两平方数之和 \quad \Leftrightarrow \quad p \equiv 1 \pmod 4$$

求具体方案：费马降阶法

②正整数$m$能表示成两平方数之和

将$m$分解成

$$m=p_1p_2...p_rM^2$$

其中$p_1,p_2,...,p_r$是互不相同的素因子

条件： $$p_i=2~或~p_i \equiv 1 \pmod 4 \quad (i \in [1,r])$$

②正整数$m$能表示成$m=a^2+b^2$且$gcd(a,b)=1$

条件：

$$m \mod 2=1 ~且~ p \equiv 1 \pmod 4 ~ (p|m)$$

$$m \mod 2=0 ~且~ m/2 \mod 2=1  ~且~ p \equiv 1 \pmod 4 ~ (p|m/2)$$

③c能表示成$c^2=a^2+b^2$且$gcd(a,b)=1$

条件：

$$p \equiv 1 \pmod 4 ~ (p|c)$$