# 模平方和

$$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$$即为方程的解
