> For the complete documentation index, see [llms.txt](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/er-ci-tong-yu-shi-he-ping-fang-sheng-yu/mo-ping-fang-gen.md).

# 模平方根

## **模**$$4k+3$$**平方根**

$$p$$为形如$$4k+3$$的素数，求同余式$$x^2\equiv a\left(\mod p\right)$$

> * **STEP1: 二次互反律验证有解**
>
>   $$a^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\equiv 1\left(\mod p\right)$$
> * **STEP2: 定理**
>
>   解为$$x\equiv \pm a^{\frac{p+1}{4}}\left(\mod p\right)$$

## **模**$$4k+1$$**平方根**

$$p$$为奇素数，$$p-1=2^t\cdot s$$，$$t\geq 1$$，$$s$$为奇数，求同余式$$x^2\equiv a\left(\mod p\right)$$

> * **STEP1: 验证有解**
> * **STEP2: 求解**$$b$$**和**$$a^{-1}$$
>
>   $$n$$为模$$p$$的平方非剩余，$$b=n^s\left(\mod p\right)$$
> * **STEP3: 求解**
>
>   $$x\_{t-1}\equiv a^{\frac{s+1}{2}}\left(\mod p\right)$$
>
>   $$j\_{k-1}=\left{ \begin{array}{**lr**} 0 &{\left(a^{-1}x\_{t-k}^{2}\right)}^{2^{t-k-1}}\equiv1\left(\mod p\right)\ 1 &{\left(a^{-1}x\_{t-k}^{2}\right)}^{2^{t-k-1}}\equiv -1\left(\mod p\right) \end{array} \right.$$
>
>   $$x\_{t-k-1}=x\_{t-k}b^{j\_{k-1}2^{k-1}}$$
> * $$x\_0$$为解

## **模**$$m$$**平方根**

$$m=2^{\delta}\cdot p\_{1}^{{\alpha}*1}\cdots p*{k}^{{\alpha}\_k}$$

> * **STEP1: 等价同余式组**
>
>   原同余式等价于
>
>   $$\left{ \begin{array}{**lr**} x^2\equiv a\left(\mod 2^{\delta}\right)\ x^2\equiv a\left(\mod p\_{1}^{{\alpha}*1}\right)\ \cdots\ x^2\equiv a\left(\mod p*{k}^{{\alpha}\_k}\right) \end{array} \right.$$
> * **STEP2: 求**$$x^2\equiv a\left(\mod p^{\alpha}\right)$$
>   * 求$$x^2\equiv a\left(\mod p\right)$$
>   * 若$$\alpha>1$$，使用高次同余式求解方法求$$x^2-a\equiv0\left(\mod p^{\alpha}\right)$$有解的条件及个数
> * **STEP3: 求**$$x^2\equiv a\left(\mod 2^{\alpha}\right)$$
>   * 验证有解
>
>     $$\left{ \begin{array}{**lr**} a\equiv 1\left(\mod 4\right) &\alpha=2\ a\equiv 1\left(\mod 8\right) &\alpha\geq3 \end{array} \right.$$
>   * 求解
>     * $$\alpha=2$$
>
>       $$x\equiv\pm1\left(\mod 4\right)$$
>     * $$\alpha=3$$
>
>       $$x\equiv\pm1,\pm3\left(\mod 8\right)$$
>     * $$\alpha\geq4$$
>
>       若同余式$$x^2\equiv a\left(\mod 2^{\alpha-1}\right)$$的解为$$x=\pm\left(x\_{\alpha-1}+t\_{\alpha-1}2^{\alpha-2}\right),t\_{\alpha-1}=0,\pm1,\cdots$$
>
>       $$x^2\equiv a\left(\mod 2^{\alpha}\right)$$的解为$$x=\pm\left(x\_{\alpha}+t\_{\alpha}2^{\alpha-1}\right)=\pm\left(x\_{\alpha-1}+\left(\frac{a-x\_{\alpha-1}^{2}}{2^{\alpha-1}}\left(\mod2\right)\right)\cdot2^{\alpha-2}+t\_{\alpha}2^{\alpha-1}\right),t\_{\alpha}=0,\pm1,\cdots$$
>
>       解为$$x\_{\alpha},x\_{\alpha}+2^{\alpha-1},-x\_{\alpha},-\left(x\_{\alpha}+2^{\alpha-1}\right)$$
> * **STEP4: 利用中国剩余定理求解**