那個簡單組中的 DLP 有多難？
讓 $ p=4q-1 $ 成為素數 $ q $ 一個奇怪的素數。讓 $ G={0,1,\dots,p-1,\infty} $ . 以下法律 $ * $ 使 $ (G,*) $ 可交換的序群 $ 4q $ 中性元素 $ \infty $ :
$$ a*b=\begin{cases} a&\text{if }b=\infty\ b&\text{if }a=\infty\ \infty&\text{if }a\ne\infty\text{ and }b\ne\infty\text{ and }a+b\equiv 0\pmod p\ {ab-1\over a+b}\bmod p&\text{otherwise}\end{cases} $$ 的倒數 $ a $ 對於法律 $ * $ 是 $ p-a $ , 除了 $ 0 $ 和 $ \infty $ 這是他們自己的逆。關聯性的證明需要小心，並使用 $ p\equiv3\bmod4 $ 在某一點。 計算可以通過保留一個元素來簡化 $ G $ 作為整數分數 $ x\over y $ 和 $ x $ 和 $ y $ 整數模 $ p $ , 和中性元素 $ \infty $ 表示為 $ x\over0 $ 和 $ x\not\equiv0\pmod p $ . 沒有任何特殊情況，群定律變為：
$$ {x_a\over y_a}{x_b\over y_b}={(x_ax_b-y_ay_b)\bmod p\over(x_ay_b+y_ax_b)\bmod p} $$ 我們只需要 4 次乘法、1 次加法、1 次減法和 2 次模歸約 $ ab $ ; 減少到 2 個平方、1 個乘法、1 個加倍、1 個減法和 2 個模減少 $ a*a $ . 由於我們有一個群定律，我們可以定義取冪。指數可以減少模 $ 4q $ , 組的順序。
讓 $ g $ 成為秩序的要素 $ q $ . 可以啟發式地找到它，也許從 $ g=2 $ 增量和檢查 $ g^4\ne\infty $ 和 $ g^q=\infty $ （當我們不在乎時，Poncho 的評論提供了一種更快的方法 $ g $ 很大）。
問題：素數循環子群中的離散對數問題有多難 $ q $ 由產生 $ g $ ? 是不是和某個知名的團體有點關係？
更新：公式 $ x_{ab}=(x_ax_b-y_ay_b)\bmod p $ 和 $ y_{ab}=(x_ay_b+y_ax_b)\bmod p $ 與笛卡爾座標中的複數乘法相同，除了它們用於整數模 $ p $ . 現在關聯性不那麼令人驚訝了。
通過極座標，我們可以表示 $ g^k $ 對於法律 $ * $ 沒有迭代：那就是 $ ((y^{-1}\bmod p)x)\bmod p $ 為了 $ x=(g^2+1)^{k/2}\cos(k\cot^{-1}g) $ 和 $ y=(g^2+1)^{k/2}\sin(k\cot^{-1}g) $ . 數量 $ x $ 和 $ y $ 是整數，即使中間值使用實數。這在計算上是不切實際的，因為我們需要極高的精度。並且它不會導致解決 DLP 的簡單方法。
該組嵌入 $ F_{\hspace{-0.02 in}p}[i\hspace{.02 in}] $ $ ^{\hspace{.02 in}*} $ 通過由下式給出的莫比烏斯變換
$ f(x) = \dfrac{x+i}{x-i} $ （和 $ \hspace{.04 in}f(\infty) = 1 $ )，並且嵌入具有左逆
（這不是單射的，也不一定是同態）這是
莫比烏斯變換由 $ ;;; g(z) : = : \dfrac{z+1}{z-1} \cdot i ;;; $ （和 $ g(1) = \infty $ ）。
它們的部分逆性可用於找到該嵌入的範圍
（即，該範圍是該嵌入的不動點集 $ g $ );
解決表明這正是要點 $ z $ 這樣 $ g(z) $ 在嵌入的域中。
然後進一步求解給出所有元素 $ c $ 和 $ d $ 的 $ F_{\hspace{-0.02 in}p} $ ,
$ g(c\hspace{-0.03 in}+\hspace{-0.03 in}(d\hspace{-0.06 in}\cdot \hspace{-0.05 in}i\hspace{.02 in})) $ 當且僅當 $ ;;; c^{\hspace{.02 in}2}\hspace{-0.04 in}+d^{\hspace{.02 in}2} : = : 1 ;;; $ .
因此，您的組有效地等效於 mod-p circle group。
後者是一個有效域的乘法群的一個有效可判定子群， 該有效域是一個高斯整數
的簡單商，
是一個單元數很少 的唯一分解域。 因此，通過嘗試找到子組中兩個輸入 相對於整個乘法組 的同一生成器的離散對數，應該 能夠使用索引演算來 解決子組的離散對數問題，
使用
$ i $ 和非關聯G aussian 素數作為因子基礎。
出於這個原因，雖然我不知道GNFS是如何工作的，但我想
你們小組的 DLP的硬度最多不會比標準 DLP mod primes 高多少。
我不知道任何比SNFS DLP算法更快的算法
$$ subgroups whose order has a large prime factor $$一個有效領域的乘法組，所以特別是，我也不知道你的組有任何這樣的算法。
另一方面，我也不知道 SNFS 是如何工作的。