高中數學擴充套件/進階模算術/專案/求平方根

高中數學擴充套件

求平方根

.. 待擴充套件 實際上有一個簡單的方法來確定 *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求平方根的方法