有效地計算與 Z/NZ 同構的環中的中性元素？
編輯以澄清問題
所以我的問題是，是否有人知道在同構的抽象環中計算中性元素（我將其稱為 1，但運算不必是乘法）的有效方法從/ñ從 $ \mathbb Z/ N\mathbb Z $ ? 更具體地說，場景是這樣的：
假設我們有一個戒指R=從/ñ從 $ R = \mathbb Z/ N\mathbb Z $ （這裡，操作是加法和乘法）和環同構F:(R,+,⋅)→(小號,△,∗) $ f: (R,+,\cdot) \rightarrow (S, \triangle, *) $ . 但是，我們不知道這個雙射是什麼F $ f $ 是。我們還假設ñ $ N $ 非常大，就像 RSA-Modulus 一樣，因此分解是未知的。正如已經指出的，如果ñ $ N $ 是指數級的，我們不能只有一個元素列表，所以我們假設元素是通過一個黑盒子給出的，當呼叫它時輸出一個元素小號 $ S $ ，但沒有告訴我們哪個元素R $ R $ 它對應。的元素小號 $ S $ 例如，可以是位串。
DW 在他的回答中表明，如果我們只有 oracle 訪問△ $ \triangle $ 和∗ $ * $ , 中性元素關於∗ $ * $ 如果不能有效計算ñ $ N $ 不能有效地分解。所以剩下的問題是：
如果操作△ $ \triangle $ 和∗ $ * $ 以公式的形式顯式給出，我們是否總能有效地計算∗ $ * $ 因此中性元素？
或者在某些情況下，即使使用公式而不是 oracle 訪問也對我們沒有幫助？
這是一個簡短的例子：
R $ R $ 是從/7從 $ \mathbb Z/ 7\mathbb Z $ 有規律的模加法和乘法。 小號 $ S $ 是從/7從 $ \mathbb Z/ 7\mathbb Z $ ,X△是:=X+是−4反對7, X∗是:=(X−4)(是−4)+4反對7 $ x \triangle y := x + y - 4 \bmod 7, \ \ \ x * y := (x-4)(y-4) + 4 \bmod 7 $ .
所以在環小號, 和△=4 $ S, \ e_\triangle = 4 $ （我們通過求解得到這個X△和△=X∀X∈小號⇔X+和△−4=X∀X∈小號⇔和△−4=0 $ x \triangle e_\triangle = x \forall x \in S \Leftrightarrow x + e_\triangle - 4 = x \forall x \in S \Leftrightarrow e_\triangle - 4 = 0 $ ，或更一般地說，因為我們知道組的順序關於△ $ \triangle $ 是 7，即我們可以任意取X $ x $ 併計算X△X△X…△X $ x \triangle x \triangle x \dots \triangle x $ （7 次））。
但是關於和∗ $ e_* $ ? 在這個具體的例子中，我們可以很容易地解決X∗和∗=X∀X∈小號 $ x * e_* = x \forall x \in S $ 獲得和∗=5 $ e_* = 5 $ ，但我們只能解決它，因為這是一個簡單的例子。
感謝您的幫助 ：）
這是一個非常模棱兩可、提出不當的問題，所以我將以一種我覺得有趣的方式實例化它。如果這不是您想要回答的問題，請編輯您的問題以更好地提出一個格式正確的問題。
$ \newcommand{\tri}{\mathbin{\triangle}} $ 我將假設我們得到一個整數ñ $ N $ 的未知因式分解，我們有一個元素的表示從/ñ從 $ \mathbb{Z}/N\mathbb{Z} $ 作為位串，通過一些表示函式[⋅]:從/ñ從→{0,1}∗ $ [\cdot] : \mathbb{Z}/N\mathbb{Z} \to {0,1}^* $ . 因此，[X] $ [x] $ 是X∈從/ñ從 $ x \in \mathbb{Z}/N\mathbb{Z} $ . 定義操作△,∗ $ \triangle,* $ 以便[X+是]=[X]△[是] $ [x+y] = [x] \tri [y] $ 和[X是]=[X]∗[是] $ [xy] = [x] * [y] $ . 或者，換句話說，定義△ $ \tri $ 經過s△噸=[⟨s⟩+⟨噸⟩] $ s \tri t = [\langle s \rangle + \langle t \rangle ] $ 在哪裡⟨⋅⟩:{0,1}∗→從/ñ從 $ \langle \cdot \rangle : {0,1}^* \to \mathbb{Z}/N\mathbb{Z} $ 是的逆映射[⋅] $ [\cdot] $ , 同樣對於∗ $ * $ .
（就原題而言，位串起到環的作用小號 $ S $ .)
假設我們被賦予了以下能力（並且只有這些能力）：
- 我們有一個黑盒子，當它被呼叫時，會生成一個隨機元素r $ r $ 在從/ñ從 $ \mathbb{Z}/N\mathbb{Z} $ 並輸出[r] $ [r] $ （它不會告訴我們r $ r $ ， 儘管）。
- 我們有一個黑盒子，當給定s,噸 $ s,t $ 作為輸入，將輸出s△噸 $ s \tri t $ .
- 我們有一個黑盒子，當給定s,噸 $ s,t $ 作為輸入，將輸出s∗噸 $ s * t $ .
問題變成了：我們可以計算[1] $ [1] $ , 一個位串，表示1∈從/ñ從 $ 1 \in \mathbb{Z}/N\mathbb{Z} $ ? 換句話說，我們正在尋找一種通用算法，無論何種表示圖都能正常工作[⋅] $ [\cdot ] $ 恰好被選中。
答案是：不，沒有有效的算法來計算[1] $ [1] $ ，僅給出這些操作。這可以使用用於顯示通用黑盒組中的下限的相同技術來顯示，例如，使用相同的技術來顯示通用組中的離散對數不存在多項式時間通用算法。
我們如何展示它？我將首先說明一個證明，對於我們只允許呼叫第一個黑盒一次的情況：我們可以生成一個隨機值[r] $ [r] $ , 然後我們可以申請△,∗ $ \tri,* $ 多項式多次。這是證據。讓X0=r $ x_0=r $ ， 然後讓X一世 $ x_i $ 表示一世 $ i $ 第一個元素從/ñ從 $ \mathbb{Z}/N\mathbb{Z} $ 我們計算的。例如，如果我們的算法採用[r] $ [r] $ 併計算s=[r]△[r] $ s = [r]\tri [r] $ 然後計算噸=s∗[r] $ t = s*[r] $ （說），我們會有X0=r $ x_0=r $ ,X1=r+r $ x_1=r+r $ ,X2=X1X0 $ x_2=x_1x_0 $ . 假設算法執行ķ $ k $ 腳步。為了使算法正確，我們需要它輸出[1] $ [1] $ ，或者換句話說，我們需要有Xķ=1 $ x_k=1 $ . 請注意，每個X一世 $ x_i $ 可以表示為的一些多項式X0 $ x_0 $ ， 說，X一世=p一世(X0) $ x_i=p_i(x_0) $ （這可以通過歸納來證明）。所以我們的算法對應一個多項式pķ(⋅) $ p_k(\cdot) $ .
如果算法是正確的，我們必須有pķ(r)=1 $ p_k(r)=1 $ 隨機選擇的機率很高r $ r $ . 這可能嗎？事實證明這是不可能的，如果ķ $ k $ 不是太大，如果ñ $ N $ 很難考慮。特別是，如果公關r[pķ(r)=1] $ \Pr_r[p_k(r)=1] $ 很大，那麼我們得到一個分解算法ñ $ N $ 和ķ $ k $ 步驟並且具有非常大的成功機率。這就是為什麼。定義多項式q(⋅) $ q(\cdot) $ 經過q(X)=pķ(X)−1 $ q(x)=p_k(x)-1 $ . 根據假設，公關r[q(r)=0] $ \Pr_r[q(r)=0] $ 很大，即多項式q(X) $ q(x) $ 有很多根。另一方面，它不能有太多的根：它最多有ķ2 $ k^2 $ 根，通過中國剩餘定理的簡單應用，所以如果ķ $ k $ 小於√ñ $ \sqrt{N} $ ,公關r[q(r)=0] $ \Pr_r[q(r)=0] $ 大但嚴格小於1 $ 1 $ . 現在假設ñ=磷問 $ N=PQ $ ，並考慮多項式q(X)反對磷 $ q(x) \bmod P $ 和q(X)反對問 $ q(x) \bmod Q $ . 請注意
公關r[q(r)=0]=ε磷×ε問
$$ \Pr_r[q(r)=0] = \epsilon_P \times \epsilon_Q $$ 在哪裡ε磷=公關r[q(r)=0(反對磷)] $ \epsilon_P = \Pr_r[q(r)=0 \pmod P] $ 和ε問=公關r[q(r)=0(反對問)]. $ \epsilon_Q = \Pr_r[q(r)=0 \pmod Q]. $
由於左側（公關[q(r)=0] $ \Pr[q(r)=0] $ ) 很大，那麼右邊的兩個項 (ε磷,ε問 $ \epsilon_P,\epsilon_Q $ ) 必須很大。尤其，q $ q $ 有很多根模磷 $ P $ 和許多根模問 $ Q $ . 所以，這是一個有效的分解算法ñ $ N $ . 我們挑選r $ r $ 隨機，計算q(r) $ q(r) $ ，然後計算gcd(ñ,q(r)) $ \gcd(N,q(r)) $ . 請注意，這會輸出一個重要的因素ñ $ N $ 有機率ε磷(1−ε問)+ε問(1−ε磷) $ \epsilon_P (1-\epsilon_Q) + \epsilon_Q (1-\epsilon_P) $ . 自從ε磷×ε問<1 $ \epsilon_P \times \epsilon_Q < 1 $ 但兩者ε磷,ε問 $ \epsilon_P,\epsilon_Q $ 很大，因此ε磷(1−ε問)+ε問(1−ε磷) $ \epsilon_P (1-\epsilon_Q) + \epsilon_Q (1-\epsilon_P) $ 很大，即這種因式分解的算法ñ $ N $ 有很大的成功機率。
所以這是一個減少，它表明任何對該問題的有效解決方案都會立即產生一個有效的分解算法。因此，我們不應該期望任何有效的解決方案來解決這個問題（因為我們不期望有任何有效的分解算法）。減少是緊張的，因為我在評論中已經表明，如果你可以考慮ñ $ N $ , 那麼這個問題就很容易解決了。
從技術上講，我只證明了只呼叫第一個黑盒（生成隨機值的黑盒）的算法的結果[r] $ [r] $ ）。然而，通過查看多元多項式而不是單變數多項式，這種證明技術可以擴展到對第一個黑盒進行任何可行數量呼叫的算法。這些基本上是相同的技術，用於表明沒有執行比平方根時間更快的離散日誌（在通用/黑盒組中）的通用算法。