模平方和

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