x2+y2=px^2+y^2=px2+y2=p
STEP1: 求m0m_0m0寻找x=x0x=x_0x=x0，使得x2≡−1(mod p)x^2\equiv-1\left(\mod p\right)x2≡−1(modp)，存在y0=1y_0=1y0=1使得x02+y02=m0⋅px_0^2+y_0^2=m_0\cdot px02+y02=m0⋅pSTEP2:求ui,viu_i, v_iui,viui≡xi(mod mi)u_i\equiv x_i\left(\mod m_i\right)ui≡xi(modmi)vi≡yi(mod mi)v_i\equiv y_i\left(\mod m_i\right)vi≡yi(modmi)STEP3: 求xi,yix_i, y_ixi,yixi+1=ui⋅xi+vi⋅yimix_{i+1}=\frac{u_i\cdot x_i+v_i\cdot y_i}{m_i}xi+1=miui⋅xi+vi⋅yiyi+1=ui⋅yi−vi⋅ximiy_{i+1}=\frac{u_i\cdot y_i-v_i\cdot x_i}{m_i}yi+1=miui⋅yi−vi⋅xiSTEP4: 求mim_imixi2+yi2=mi⋅px_i^2+y_i^2=m_i\cdot pxi2+yi2=mi⋅p当mk=1m_k=1mk=1时，xk,ykx_k,y_kxk,yk即为方程的解
STEP1: 求m0m_0m0
寻找x=x0x=x_0x=x0，使得x2≡−1(mod p)x^2\equiv-1\left(\mod p\right)x2≡−1(modp)，存在y0=1y_0=1y0=1使得x02+y02=m0⋅px_0^2+y_0^2=m_0\cdot px02+y02=m0⋅p
STEP2:求ui,viu_i, v_iui,vi
ui≡xi(mod mi)u_i\equiv x_i\left(\mod m_i\right)ui≡xi(modmi)
vi≡yi(mod mi)v_i\equiv y_i\left(\mod m_i\right)vi≡yi(modmi)
STEP3: 求xi,yix_i, y_ixi,yi
xi+1=ui⋅xi+vi⋅yimix_{i+1}=\frac{u_i\cdot x_i+v_i\cdot y_i}{m_i}xi+1=miui⋅xi+vi⋅yi
yi+1=ui⋅yi−vi⋅ximiy_{i+1}=\frac{u_i\cdot y_i-v_i\cdot x_i}{m_i}yi+1=miui⋅yi−vi⋅xi
STEP4: 求mim_imi
xi2+yi2=mi⋅px_i^2+y_i^2=m_i\cdot pxi2+yi2=mi⋅p
当mk=1m_k=1mk=1时，xk,ykx_k,y_kxk,yk即为方程的解
最后更新于3年前