x²≡a mod p（p为奇素数）的解法

索引

• 关于p=4m+3的情形
  • • 示例

  • 涉及p=8m+5的情形

  • • 示例

  • 针对p=8m+1的情形（已知N为模p下的平方非剩余数）

  • • 示例

  • 其他情形

p=4m+3的数学分析

在已知同余方程存在解的前提下，

1. 若\left. p \right|a，则原始同余方程可转化为
   {{x}^{2}}\equiv a\equiv 0\text{ }\bmod p
   此情况下仅存在一个解
   x\equiv 0\text{ }\bmod p

2. 若p不整除a，由于p=4m+3为奇素数，且a是模p下的平方剩余，根据欧拉判别法可知
   \begin{aligned} & \text{ }{ {a}^{\frac{p-1}{2}}}={ {a}^{\frac{4m+3-1}{2}}}={ {a}^{2m+1}}\equiv 1\text{ }\bmod p \\ & \Rightarrow { {x}^{2}}\equiv a=a\times 1\equiv a\times { {a}^{2m+1}}={ {\left( { {a}^{m+1}} \right)}^{2}}\text{ }\bmod p \\ \end{aligned}
   由此