如何找到具有小逆的小型發電機？對安全有負面影響嗎？（對於 Schnorr 子群Z/P從從/磷從mathbb{Z}/Pmathbb{Z})
給定一個素數 $ P $ 和 $$ P= r \cdot q+1 $$ 和 $ q $ 素數。
我在找發電機 $ g $ Schnorr子群的有序 $ q $ 它的值很小並且有一個倒數（到 $ \bmod P $ ) 這也很小： $$ |{g^i, \forall i \in [0,P-1]}| = q $$ $$ g^q = 1 \bmod P $$ $$ g < m \text{ } \land \text{ } g^{-1}<m $$
查找 Schnorr 組生成器 $ g $ 一般來說，我們可以選擇一個隨機值 $ h $ 直到 $$ h^r \not= 1 \bmod P $$ $$ \rightarrow \text{ } g = h^r \bmod P $$ 尋找 $ g^{-1} $ 我們可以使用擴展歐幾里得算法或只計算： $$ g^{-1} = g^{q-1} \bmod P $$
問題：
Q1.) 最好的查找方法是什麼 $ g,g^{-1} $ 每個都小於值 $ m $ ?（編輯：通過逐步計算找到一些。現在的主要興趣是第三季度（編輯結束））第二季度。）有多小可以 $ m $ 是？
Q3.) 會不會小 $ g,g^{-1} $ 對安全有影響嗎？
**Q1 試用：**尋找小物的方法 $ g, g^{-1} $
a.) 隨機選擇 $ v $ Schnorr 集團的編號和項目 $ v_s = v^r \bmod P $
（所有值，但 $ 1 $ Schnorr 組的一個是生成器）
b.）用 EEA 或用 $ v_s^{q-1} \bmod P $ （任何方式更快？）
c.）檢查是否 $ g, g^{-1} < m $ . 如果不重複 a.)b.)c.)
始終隨機選擇的另一種方法是初始隨機選擇 $ g $ ，以及第二個隨機值 $ w $ 從這個組開始。計算兩者的逆並使用新生成器遍歷組 $ g^_j $ : $$ g_j^ = w \cdot (g)^j \bmod P $$ $$ {g_j^}^{-1} = w^{-1} \cdot (g^{-1})^j \bmod P $$ $$ w \cdot (g)^j \cdot w^{-1} \cdot (g^{-1})^j = 1 \bmod P $$ 並測試是否 $ g^_j $ 並且它的倒數小於 $ m $ .
這可以更快地計算值，但是找到合適的生成器會更快嗎？對於某些價值觀，結果是否會出現在糟糕價值觀的低谷中？
**Q2試用：**能小到什麼程度 $ m $ 是？
的產品 $ g, g^{-1} $ 至少需要 $ p+1 $
這意味著 $ m \ge \sqrt{p-1} $
最小的是否有另一個更高的邊界 $ m $ ?
一般來說，等式需要成立： $$ g \cdot g^{-1} = a\cdot P +1 \equiv 1 \bmod P $$ $$ a \in [1,P-2] $$
是否可以因式分解 $ (aP+1) $ 用於求解 Q1 ( $ g,g^{-1} $ 因子的產品（組合））？
有什麼辦法可以保證它在 Schnorr 集團內？
或者只是再次檢查 $ g^q = 1 \bmod P $ ?
Q3.) 會不會小 $ g, g^{-1} $ 對安全有影響嗎？
它不會出現這樣的。很容易證明，如果我們有一個生成器 $ g $ 這使得離散對數（或計算 Diffie-Hellman）問題變得容易，那麼離散對數/CDH 問題對於任何基礎都很容易 $ h $ 那是在同一個子組內。
假設我們有一種方法，給定 $ g, g^x $ ，給了我們價值 $ x $ . 那麼，我們能做些什麼，給定 $ h, h^y $ 是先找到值 $ z $ 這樣 $ g^z = h $ （通過將離散對數求解到基 $ g $ )，然後是值 $ w $ 這樣 $ g^w = h^y $ （再次，將另一個離散對數求解到基 $ g $ ); 那麼，我們有 $ h^{wz^{-1}} = h^y $ ; 因為我們知道 $ w $ 和 $ z $ ，這告訴我們離散對數。類似（但更複雜）的邏輯允許我們解決計算 Diffie-Hellman 問題，給定一個 CDH 預言機關於 base $ g $ .
但是，這不是問題的完整答案；這可能是一個小的存在 $ g, g^{-1} $ 使所有離散對數/CDH 問題變得容易。
我不知道有什麼方法可以證明這一點。然而：
- 已知的離散對數方法都沒有顯著的加速 $ g, g^{-1} $ （重要的是，我的意思不僅僅是加快乘以 $ g $ )
- 對於幾乎任何素數，都會有微小的 $ g $ 生成包含 Schnorr 組作為子組的組的值。如果有一種快速的方法來完成離散日誌 $ g $ 在這個組中，那麼你可以用它來計算 Schnorr 組中的離散日誌（雖然這個論點沒有考慮到微小的 $ g^{-1} $ ，沒有明顯的方法來使用它）。