模平方根
模平方根
为形如的素数,求同余式
STEP1: 二次互反律验证有解
STEP2: 定理
解为
模平方根
为奇素数,,,为奇数,求同余式
STEP1: 验证有解
STEP2: 求解和
为模的平方非剩余,
STEP3: 求解
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.
为解
模平方根
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: 求
求
若,使用高次同余式求解方法求有解的条件及个数
STEP3: 求
验证有解
\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.
求解
若同余式的解为
的解为
解为
STEP4: 利用中国剩余定理求解
最后更新于
这有帮助吗?