在十字路口分解理想
讓 $ R $ 做一個環，讓 $ (a),(b) $ 是由產生的理想 $ a,b\in R $ 分別。讓 $ c=a\cdot b $ 和 $ (c) $ 產生的理想 $ c $ .
我假設，鑑於 $ c $ , 計算上很難推導出 $ a,b $ （因為單位組 $ R $ 很大）。假設我們得到 $ c $ 我們有一個測試功能 $ T:R\to {0,1} $ 如果輸入在，則輸出 1 $ {a,b} $ 否則為 0。
是參數化理想列表的算法嗎 $ I_1,I_2 $ 這樣 $ (c)=I_1\cap I_2 $ ? 在我看來，編寫所有此類分解與列出所有解決方案基本相同 $ x,y $ 這樣 $ c=xy\in R $ . 是這樣嗎？
我對特定案例感興趣 $ R=\mathbb{Z}[x]/(x^{2^k}+1) $ , 和的係數 $ a,b $ 在幅度上受 $ B\in \mathbb{Z}_+, B>2 $ .
對於所有單位 $ u $ , $ (a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u)\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b\hspace{-0.02 in}\right) $ 是一個因式分解 $ c $ , 和 $ a^{-1} \hspace{-0.06 in}\cdot \hspace{-0.04 in}(a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u) $ 和 $ \left(\hspace{-0.04 in}\left(\hspace{-0.02 in}u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b\hspace{-0.02 in}\right)\hspace{-0.06 in}\cdot \hspace{-0.04 in}b^{-1}\hspace{-0.04 in}\right)^{\hspace{.04 in}-1} $ 都給 $ u $ ， 所以
$$ either factor and which side it is $$足以推斷 $ u $ .
設“修正因子”為 $ a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u $ 和 $ u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b $ , 設 N 為單位數，
假設猜測者最多進行 q+1 次猜測。
遊戲 0：猜猜者獲勝當且僅當其至少有一個猜測是 $ u $ . 遊戲 1：猜猜者獲勝當且僅當其至少有一個
猜測是
$$ either modified factor and the modified factor’s side $$. 遊戲 2：當且僅當
它的至少一個猜測是至少一個修正因子時，猜者獲勝。
遊戲 3： 猜測者最多可以將其猜測之一指示為“最終”，但無論如何，
當且僅當它的至少一個猜測是修正因子中的至少一個時，它才會獲勝。
遊戲4：
在每次未指示為最終的猜測之後，向猜測者發送 0。
當且僅當其至少一個猜測是修改後的因子中的至少一個時，猜測者獲勝。
遊戲5：
每次之後
$$ guess that’s not indicated as final $$不是修正因子之一，
則向猜測者發送 0 。
$$ guess that’s not indicated as final $$這是修正因子之一，猜測者被發送 1。
當且僅當其至少一個猜測是修正因子中的至少一個時，猜測者獲勝。 遊戲6：
每次之後
$$ guess that’s not indicated as final $$不是修正因子之一，
則向猜測者發送 0 。
$$ guess that’s not indicated as final $$這是修改的因素之一，猜測者被發送 1. 猜測者獲勝當且僅當
$$ it indicated a guess as final $$這個猜測至少是修改後的因素之一。 遊戲7：
每次之後
$$ guess that’s not indicated as final $$不是修正因子之一，
則向猜測者發送 0 。
$$ guess that’s not indicated as final $$這是修改的因素之一，猜測者被發送 1. 猜測者獲勝當且僅當
$$ it indicated a guess as final $$這個猜測是修正後的因素。 遊戲8：
每次之後
$$ guess that’s not indicated as final $$這不是其中之一 $ {\hspace{-0.02 in}a,\hspace{-0.02 in}b\hspace{-0.02 in}} $ , 猜測者被發送 0。$$ guess that’s not indicated as final $$這是其中之一 $ {\hspace{-0.02 in}a,\hspace{-0.02 in}b\hspace{-0.02 in}} $ , 猜測者被發送 1.
猜測者獲勝當且僅當$$ it indicated a guess as final $$這個猜測是 $ a,\hspace{-0.02 in}b $ .
在第 0 場比賽中，對於 N 個等可能的可能性，只有 q+1 次猜測，
所以第 0 場比賽獲勝的機率最多為 (q+1)/N。 如前所述， $ u $ 可以從
$$ either modified factor and the
modified factor’s side $$，因此對於每個第 1 局的猜測者，都有一個具有
相同獲勝機率的第 0 局的猜測者。 因此，贏得第 1 局遊戲的機率也最多為 (q+1)/N。 對於每個第 2 局的猜者，有一個第 1 局的猜者有一半的獲勝機率（只是隨機猜邊），所以第 2 局獲勝的機率最多是第 1 局獲勝的最大機率的兩倍。因此機率贏得比賽 2 的機率最多為 (2*(q+1))/N。
對於每個第 3 局的猜者，有一個具有相同獲勝機率的第 2 局的猜者。
（只需忽略“最終”指示的存在與否。）
因此，贏得第 3 場比賽的機率最多為 (2*(q+1))/N。
對於每個第 4 局的猜者，都有一個具有相同獲勝機率的第 3 局的猜者。
（只是在每次未指示為最終的猜測之後發送 0。）
因此贏得第 4 場比賽的機率最多為 (2*(q+1))/N。
遊戲 4 和遊戲 5 僅在已經保證獲勝的情況下有所不同，
因此贏得遊戲 5 的機率最多為 (2*(q+1))/N。
第六局獲勝條件和第五局獲勝條件的唯一區別在於
前者的獲勝條件是對後者獲勝條件的限制，所以第五局獲勝的機率最多為(2*(q+1))/N。
對於每個第 7 局的猜測者，都有一個
至少有同樣大的獲勝機率的第 6 局的猜測者。
（只需選擇其指示為最終猜測的一部分）。
因此，贏得第 7 場比賽的機率最多為 (2*(q+1))/N。
對於每個 $ u $ , 方程 $ ;;; a\cdot u : = : c ;;; $ 和 $ ;;; u^{-1} \cdot b : = : d ;;; $ 兩者都有一個唯一的解決方案，所以正好有 N 個選擇 $ a,\hspace{-0.02 in}b,\hspace{-0.02 in}u $ 產量修正因子 $ c,\hspace{-0.02 in}d $ . $ ;;;;;;;; $ 這意味著
修正因子的分佈是均勻的，因此與 $ a,\hspace{-0.02 in}b $ . 因此，贏得第 8 場比賽的機率最多為 (2*(q+1))/N。
最後，請注意第 8 場比賽正是用於猜測的比賽 $ a,\hspace{-0.02 in}b $ 給定 $ c $ 和
$$ at most q queries to the test function $$. 因此，對於所有最多進行 q 次預言機查詢的對手，他們的成功機率最多為 (2*(q+1))/N，其中 N 是單元數。
正如克里斯·佩克特所說，
輸入： $ R $
輸出： $ R,\hspace{-0.02 in}R $
是“一種參數化理想列表的算法 $ I_1,I_2 $ 這樣 $ (c)=I_1\cap I_2 $ ”。
這將與“列出所有解決方案相同” $ x,y $
這樣 $ c=xy\in R $ “至少當 $ R $ 是可交換的。
（有限可能也足夠了；我現在無法弄清楚。）