高中数学扩展/进阶模算术/项目/求平方根

高中数学扩展

求平方根

.. 待扩展 实际上有一个简单的方法来确定 *a* 是否为平方

令 *g* 为 *G* 的生成元，其中 *G* 是模 *p* 的乘法群。由于所有平方数形成一个群，因此，如果 *a* 是一个平方数，那么

a^{\frac {p-1}{2}}\equiv 1

如果 *a* 不是一个平方数，那么

a^{\frac {p-1}{2}}\equiv -1

我们将在下一部分使用这些事实。 .. 待扩展

我们旨在描述一种在模m中找到平方根的方法。让我们从最简单的情况开始，其中p是素数。事实上，对于平方根的求解，最简单的情况恰好是最困难的。

如果p ≡ 3 (mod 4) 那么找到平方根很容易。请注意，如果a有平方根，那么

(a^{\frac {p+1}{4}})^{2}\equiv a^{\frac {p+1}{2}}\equiv a^{\frac {p-1}{2}}a\equiv a

所以让我们考虑模4余1的素数。假设我们可以找到a模p的平方根，并设

x_{0}^{2}\equiv a{\pmod {p}}

有了以上信息，我们可以找到a模p²的平方。我们设

x=x_{0}+x_{1}p\!

我们想要x² ≡ a (mod p²)，所以

x^{2}=x_{0}^{2}+2x_{0}x_{1}p+x_{1}^{2}p^{2}\!

x^{2}=a+kp+2x_{0}x_{1}p{\pmod {p^{2}}}\!

对于某个k，因为 $x_{0}^{2}\equiv a{\pmod {p}}$ ，所以 $x_{0}^{2}=a+kp$ ，我们可以看到

x^{2}=a+p(k+2x_{0}x_{1}){\pmod {p^{2}}}\!

所以如果我们需要找到 $x_{1}$ ，使得 $k+2x_{0}x_{1}\equiv 0{\pmod {p}}$ ，我们只需要将 $x_{1}$ 作为未知数

x_{1}\equiv -k(2x_{0})^{-1}{\pmod {p}}

.

...推广 ...示例

... 模p求平方根的方法