> 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-he.md).

# 模平方和

$$x^2+y^2=p$$

> * **STEP1: 求**$$m\_0$$
>
>   寻找$$x=x\_0$$，使得$$x^2\equiv-1\left(\mod p\right)$$，存在$$y\_0=1$$使得$$x\_0^2+y\_0^2=m\_0\cdot p$$
> * **STEP2:求**$$u\_i, v\_i$$
>
>   $$u\_i\equiv x\_i\left(\mod m\_i\right)$$
>
>   $$v\_i\equiv y\_i\left(\mod m\_i\right)$$
> * **STEP3: 求**$$x\_i, y\_i$$
>
>   $$x\_{i+1}=\frac{u\_i\cdot x\_i+v\_i\cdot y\_i}{m\_i}$$
>
>   $$y\_{i+1}=\frac{u\_i\cdot y\_i-v\_i\cdot x\_i}{m\_i}$$
> * **STEP4: 求**$$m\_i$$
>
>   $$x\_i^2+y\_i^2=m\_i\cdot p$$
>
>   当$$m\_k=1$$时，$$x\_k,y\_k$$即为方程的解