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)
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)
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−1nnn为模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)jk−1={0(a−1xt−k2)2t−k−1≡1(modp)1(a−1xt−k2)2t−k−1≡−1(modp)xt−k−1=xt−kbjk−12k−1x_{t-k-1}=x_{t-k}b^{j_{k-1}2^{k-1}}xt−k−1=xt−kbjk−12k−1x0x_0x0为解
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)
jk−1={0(a−1xt−k2)2t−k−1≡1(modp)1(a−1xt−k2)2t−k−1≡−1(modp)
xt−k−1=xt−kbjk−12k−1x_{t-k-1}=x_{t-k}b^{j_{k-1}2^{k-1}}xt−k−1=xt−kbjk−12k−1
x0x_0x0为解
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: 等价同余式组原同余式等价于{x2≡a(mod2δ)x2≡a(modp1α1)⋯x2≡a(modpkαk)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α)验证有解{a≡1(mod4)α=2a≡1(mod8)α≥3求解α=2\alpha=2α=2x≡±1(mod 4)x\equiv\pm1\left(\mod 4\right)x≡±1(mod4)α=3\alpha=3α=3x≡±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α−12α−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: 利用中国剩余定理求解
STEP1: 等价同余式组
原同余式等价于
{x2≡a(mod2δ)x2≡a(modp1α1)⋯x2≡a(modpkαk)
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α)
验证有解
{a≡1(mod4)α=2a≡1(mod8)α≥3
求解
α=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α−12α−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: 利用中国剩余定理求解
最后更新于4年前
这有帮助吗？