信息安全数学基础
  • 导读
  • 第一章 整数的可除性
    • 素数的判断
    • 广义欧几里得除法
    • 贝祖等式
    • gcd & lcm
    • 线性丢番图方程
  • 第二章 同余
    • 同余的性质
    • 剩余
    • 欧拉函数
    • 同余定理
    • 模重复平方计算法
    • RSA加密
  • 第三章 同余式
    • 一次同余式
    • 同余式组求解
    • 复杂取模运算简化
    • 高次同余式
    • 素数模的同余式简化
  • 第四章 二次同余式和平方剩余
    • 二次同余式化简
    • 二次剩余
    • Lengendre符号
    • 模p平方剩余判断
    • 雅可比符号
    • 模平方根
    • Rabin加密
    • 模平方和
  • 第五章 原根与指标
    • 指数
    • 原根
    • 指标
    • n次同余式
    • ElGamal加密
  • 第六章 素性检验
    • 伪素数和Fermat素性检验
    • Euler伪素数和Solovay-Stassen素性检验
    • 强伪素数和Miller-Rabin Primality素性检验
    • 梅森素数和Lucas-Lehmer Primality素性检验
    • 随机数生成
  • 第七章 群
    • 群和子群
    • 正规子群和商群
    • 同态和同构
    • 循环群
    • 置换群
  • 第八章 环与域
    • 环
    • 环与域
    • 多项式环
    • 有限域
  • 第九章 椭圆曲线
    • 基本概念
    • 椭圆曲线加法
    • ElGamal加密
由 GitBook 提供支持
在本页
  • 模平方根
  • 模平方根
  • 模平方根

这有帮助吗?

  1. 第四章 二次同余式和平方剩余

模平方根

模4k+34k+34k+3平方根

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

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

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

  • STEP2: 定理

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

模4k+14k+14k+1平方根

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

  • STEP1: 验证有解

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

    nnn为模ppp的平方非剩余,b=ns(mod  p)b=n^s\left(\mod p\right)b=ns(modp)

  • STEP3: 求解

    xt−1≡as+12(mod  p)x_{t-1}\equiv a^{\frac{s+1}{2}}\left(\mod p\right)xt−1​≡a2s+1​(modp)

    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}}xt−k−1​=xt−k​bjk−1​2k−1

  • x0x_0x0​为解

模mmm平方根

m=2δ⋅p1α1⋯pkαkm=2^{\delta}\cdot p_{1}^{{\alpha}_1}\cdots p_{k}^{{\alpha}_k}m=2δ⋅p1α1​​⋯pkα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(modpα)

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

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

  • STEP3: 求x2≡a(mod  2α)x^2\equiv a\left(\mod 2^{\alpha}\right)x2≡a(mod2α)

    • 验证有解

      \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α=2

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

      • α=3\alpha=3α=3

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

      • α≥4\alpha\geq4α≥4

        若同余式x2≡a(mod  2α−1)x^2\equiv a\left(\mod 2^{\alpha-1}\right)x2≡a(mod2α−1)的解为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,\cdotsx=±(xα−1​+tα−1​2α−2),tα−1​=0,±1,⋯

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

        解为xα,xα+2α−1,−xα,−(xα+2α−1)x_{\alpha},x_{\alpha}+2^{\alpha-1},-x_{\alpha},-\left(x_{\alpha}+2^{\alpha-1}\right)xα​,xα​+2α−1,−xα​,−(xα​+2α−1)

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

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

最后更新于4年前

这有帮助吗?