我們如何有效地計算組中某些元素的 sqrt？
我只知道一種方法，如果這個群是一個循環群，我們知道元素可以表示為 $ g^m $ ， 然後 $ g^{(m/2)} $ 是答案。
- 另一個問題，如果 $ m $ 是一個奇數，我們能確定沒有答案嗎？
- 是否有可能找到另一個發電機 $ g_1 $ 和一個偶數 $ k $ 滿足元素 = $ g_1^k $ ?
如果我們不知道該組是否是循環組，那麼找到 sqrt 或確認不存在這樣的答案的複雜性與 DLP 一樣困難嗎？
TL;DR：高效算法僅存在於特定情況下。這個問題，在其完全一般性（有限阿貝爾群）等價於整數分解問題。
我們如何有效地計算組中元素的平方根？
我們可以計算平方根的一種情況是當組順序已知並且它是奇數時。任何元素 $ g $ 在一個組中具有以下屬性：如果 $ q $ 是組的順序，那麼 $ g^q=1 $ . 這是由於拉格拉格定理。等效地， $ g^{q+1}=g $ . 如果 $ q $ 那麼奇怪 $ \frac{q+1}{2} $ 是一個整數，因此我們可以計算 $ h:= g^{\frac{q+1}{2}} $ ，這是一個平方根 $ g $ .
另一種情況如下：假設 $ G $ 同構於的直接乘積群 $ k $ 2階組和奇階組的副本 $ q $ : $$ G \simeq \mathbb{G}q \times \prod{i=1}^k \mathbb{Z}_2 $$ 在哪裡 $ \mathbb{G}_q $ 表示一組順序 $ q $ 和 $ \mathbb{Z}_2 $ 2 階群。另外，重要的是，假設你知道如何計算這個同構。
在 2 階群中，非單位元素是它自己的逆元，因此它沒有平方根。這意味著以下內容：讓 $ g \in G $ . 應用同構以獲得 $ g $ 作為上述直接產品中的一個元素： $ g = (g’, g_1, …, g_k) $ ， 在哪裡 $ g’ \in \mathbb{G}_q $ 和 $ g_i $ 在裡面 $ i $ ’th $ \mathbb{Z}_2 $ . 如果存在 $ i $ 這樣 $ g_i $ 不是單位元素，那麼 $ g $ 沒有平方根。
另一方面，如果 $ g_i $ 是所有副本中的單位元素 $ \mathbb{G}_2 $ ，那麼問題就歸結為一組奇序的情況：你只需加註 $ g $ 的力量 $ \frac{q+1}{2} $ .
另一個問題，如果 $ m $ 是一個奇數，我們能確定沒有答案嗎？
不，上面也解釋了這一點。其實，對於以上內容，你不需要知道 $ m $ （通常是這種情況）。
是否有可能找到另一個發電機 $ g_1 $ 和一個偶數 $ k $ 滿足元素等於 $ g^k $ ?
上面也解決了這個問題，因為它完全描述了組中的一組正方形。
編輯：
在“Oded Goldreich，計算複雜性：概念視角”中，表明求平方根模複合數是一個等效於整數分解的計算問題。因此，不要指望任何“通用”算法，只有特殊情況的算法。一種這樣的情況是素數域中可逆元素的乘法群 $ p $ - 稱為 Tonelli-Shanks。