模平方根

模$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: 利用中国剩余定理求解