模平方根

模4k+34k+3平方根

pp为形如4k+34k+3的素数，求同余式x2≡a(mod  p)x^2\equiv a\left(\mod p\right)

  • STEP1: 二次互反律验证有解

    ap−12≡(ap)≡1(mod  p)a^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\equiv 1\left(\mod p\right)

  • STEP2: 定理

    解为x≡±ap+14(mod  p)x\equiv \pm a^{\frac{p+1}{4}}\left(\mod p\right)

模4k+14k+1平方根

pp为奇素数，p−1=2t⋅sp-1=2^t\cdot s，t≥1t\geq 1，ss为奇数，求同余式x2≡a(mod  p)x^2\equiv a\left(\mod p\right)

  • STEP1: 验证有解

  • STEP2: 求解bb和a−1a^{-1}

    nn为模pp的平方非剩余，b=ns(mod  p)b=n^s\left(\mod p\right)

  • STEP3: 求解

    xt−1≡as+12(mod  p)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.

    xt−k−1=xt−kbjk−12k−1x_{t-k-1}=x_{t-k}b^{j_{k-1}2^{k-1}}

  • x0x_0为解

模mm平方根

m=2δ⋅p1α1⋯pkαkm=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: 求x2≡a(mod  pα)x^2\equiv a\left(\mod p^{\alpha}\right)

    • 求x2≡a(mod  p)x^2\equiv a\left(\mod p\right)

    • 若α>1\alpha>1，使用高次同余式求解方法求x2−a≡0(mod  pα)x^2-a\equiv0\left(\mod p^{\alpha}\right)有解的条件及个数

  • STEP3: 求x2≡a(mod  2α)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.

    • 求解

      • α=2\alpha=2

        x≡±1(mod  4)x\equiv\pm1\left(\mod 4\right)

      • α=3\alpha=3

        x≡±1,±3(mod  8)x\equiv\pm1,\pm3\left(\mod 8\right)

      • α≥4\alpha\geq4

        若同余式x2≡a(mod  2α−1)x^2\equiv a\left(\mod 2^{\alpha-1}\right)的解为x=±(xα−1+tα−12α−2),tα−1=0,±1,⋯x=\pm\left(x_{\alpha-1}+t_{\alpha-1}2^{\alpha-2}\right),t_{\alpha-1}=0,\pm1,\cdots

        x2≡a(mod  2α)x^2\equiv a\left(\mod 2^{\alpha}\right)的解为x=±(xα+tα2α−1)=±(xα−1+(a−xα−122α−1(mod  2))⋅2α−2+tα2α−1),tα=0,±1,⋯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α,xα+2α−1,−xα,−(xα+2α−1)x_{\alpha},x_{\alpha}+2^{\alpha-1},-x_{\alpha},-\left(x_{\alpha}+2^{\alpha-1}\right)

  • STEP4: 利用中国剩余定理求解

上一页雅可比符号下一页Rabin加密

最后更新于