為什麼這個平方根算法有效？
我一直在做一些橢圓曲線密碼學，我正在使用的一個庫有這個用於計算模平方根的稍微奇怪的算法：
讓X $ x $ 是一些二次餘數模p $ p $ 對於一些大素數p $ p $ . 讓H $ h $ 成為其中的一些元素從∖p從 $ \mathbb{Z} \setminus p\mathbb{Z} $ 這樣H2−4X $ h^2-4x $ 沒有平方根模p $ p $ . 讓在n $ V_n $ 是盧卡斯序列在0=2 $ V_0=2 $ ,在1=H $ V_1=h $ 和在n=H在n−1+X在n−2 $ V_n=hV_{n-1}+xV_{n-2} $ . 讓ķ=p+12 $ k = \frac{p+1}{2} $ . 然後在ķ=2√X $ V_k = 2\sqrt{x} $ . 這顯然比眾所周知的算法效率低p≅3反對4 $ p \cong 3 \mod 4 $ ，但顯然適用於更一般的情況
馬上，人們可能會認為這個定義是矛盾的；實際上，這種遞歸的特徵方程是通過平方根來求解的H2−4X $ h^2-4x $ ，但是，作為一個盧卡斯序列，這個不可能的項永遠不會出現在任何特定的值中在ķ $ V_k $ .
我發現的對該算法的唯一參考是作為本科水平教科書中的一個練習，這表明這可以通過一些相當簡單的數學來解決，但我嘗試過的任何方法似乎都沒有得到解決方案——計算在2p+12 $ V_{\frac{p+1}{2}}^2 $ 產量在2p+12=在2+2Xp+12=H2−2X+2Xp+12 $ V_{\frac{p+1}{2}}^2 = V_2 + 2x^{\frac{p+1}{2}} = h^2 - 2x + 2x^{\frac{p+1}{2}} $ ，它看起來幾乎不像4X $ 4x $ 我會期待的。
我相信這是 Cipolla 的算法。
整數模p $ p $ 我們稱之為Fp $ \mathbf{F}_p $ ，並且由於H2−4X $ h^2 -4x $ 是一個二次無殘差模p $ p $ , 多項式磷(是):=是2−(H2−4X)∈Fp[是] $ P(Y) := Y^2-(h^2-4x) \in \mathbf{F}_p[Y] $ 沒有根。然後我們可以修改多項式環Fp[是] $ \mathbf{F}_p[Y] $ 要得到ķ:=Fp[是]/(是2−(H2−4X)) $ \mathbf{K} := \mathbf{F}p[Y]/(Y^2-(h^2-4x)) $ （通過一些代數，我們知道它同構於Fp2 $ \mathbf{F}{p^2} $ ）。在這個領域ķ $ \mathbf{K} $ 那H2−4X $ h^2-4x $ 有一個平方根（可以認為它是不確定的是=√H2−4X $ Y = \sqrt{h^2-4x} $ )
在這個擴展領域ķ $ \mathbf{K} $ （這仍然是特色p $ p $ ， 所以(米+n)p=米p+np $ (m+n)^p = m^p+n^p $ 對全部米,n∈ķ $ m,n\in \mathbf{K} $ ) 我們有(H+√H2−4X)p=Hp+(√H2−4X)p $ \left(h + \sqrt{h^2-4x}\right)^p = h^p + (\sqrt{h^2-4x})^p $ .
根據歐拉準則，(H2−4X)p−12≅−1(反對p) $ (h^2-4x)^{\frac{p-1}{2}} \cong -1 \pmod p $ 和費馬小定理Hp≅H(反對p) $ h^p \cong h \pmod p $ ，以及在Fp $ \mathbf{F}_p $ 是一樣的ķ $ \mathbf{K} $ 在Fp $ \mathbf{F}_p $ 元素。所以 Hp+(√H2−4X)p=H+(H2−4X)p−12√H2−4X=H−√H2−4X $ h^p + (\sqrt{h^2-4x})^p = h + (h^2-4x)^{\frac{p-1}{2}} \sqrt{h^2-4x} = h - \sqrt{h^2-4x} $ .
到目前為止，通過所有這些數學，我們得出結論：(H+√H2−4X)p=H−√H2−4X $ \left(h + \sqrt{h^2-4x}\right)^p = h - \sqrt{h^2-4x} $ . 同樣的論點也產生(H−√H2−4X)p=H+√H2−4X $ \left(h - \sqrt{h^2-4x}\right)^p = h + \sqrt{h^2-4x} $ .
最後我們得到平方根X $ x $ . 清楚地4X=H2−(H2−4X)=(H+√H2−4X)(H−√H2−4X)=(H+√H2−4X)(H+√H2−4X)p=(H+√H2−4X)p+1
$$ 4x = h^2 - (h^2 - 4x) = (h + \sqrt{h^2-4x})(h - \sqrt{h^2-4x}) = (h+\sqrt{h^2-4x})(h+\sqrt{h^2-4x})^p = (h+\sqrt{h^2-4x})^{p+1} $$ 現在ķ $ k $ 盧卡斯數列的第 項在ķ:=H在ķ−1+X在ķ−2 $ V_k := hV_{k-1} + xV_{k-2} $ 是在ķ=一種ķ+bķ $ V_k = a^k + b^k $ 在哪裡一種=H+√H2−4X2 $ a = \frac{h + \sqrt{h^2-4x}}{2} $ 和b=H−√H2−4X2 $ b = \frac{h - \sqrt{h^2-4x}}{2} $ . 所以在p+12=(H+√H2−4X2)p+12+(H−√H2−4X2)p+12
$$ V_{\frac{p+1}{2}} = \left(\frac{h + \sqrt{h^2-4x}}{2}\right)^{\frac{p+1}{2}} + \left(\frac{h - \sqrt{h^2-4x}}{2}\right)^{\frac{p+1}{2}} $$ 在p+12=(12)p+12((H+√H2−4X)p+12+(H−√H2−4X)p+12)
$$ V_{\frac{p+1}{2}} = \left(\frac{1}{2}\right)^{\frac{p+1}{2}} \left( (h + \sqrt{h^2-4x})^{\frac{p+1}{2}} + (h - \sqrt{h^2-4x})^{\frac{p+1}{2}} \right) $$ 在p+12=(12)p+12(√4X+√4X)=(22p−12)√X=±2√X
$$ V_{\frac{p+1}{2}} = \left(\frac{1}{2}\right)^{\frac{p+1}{2}} ( \sqrt{4x} + \sqrt{4x}) = \left(\frac{2}{2^{\frac{p-1}{2}}}\right) \sqrt{x} = \pm 2 \sqrt{x} $$