Factoring
更多知識整數分解
假設您有一個整數，它是通過將兩個隨機數相乘產生的
$$ x_1 = a \cdot b_1 \bmod(p-1) $$在哪裡 $ a $ 和 $ b_1 $ 是相對質數 $ p-1 $ 和 $ p $ 是一個大素數。 會心 $ x_1 $ 留給你 $ p-1 $ 成對的數字 $ a $ 和 $ b_1 $ ，所以猜測正確的分解很困難（對吧？）。
如果你得到更多，你在找到正確的配對方面有什麼優勢嗎？ $ x_i $ 其中一個因素被重用？例如：
$$ x_2 = a \cdot b_2 \bmod(p-1) $$
該問題執行算術運算 $ {\mathbb Z_{p-1}}^* $ , 整數減少模 $ p-1 $ 與這個模數互質。有 $ \varphi(p-1) $ 其中，其中 $ \varphi $ 是歐拉函式。這無關緊要 $ p $ 是素數，這個問題與整數分解無關。
對於任何 $ a\in{\mathbb Z_{p-1}}^* $ ， 應用程序 $ \scr F_a:{\mathbb Z_{p-1}}^\to{\mathbb Z_{p-1}}^ $ , $ b\to x=a\cdot b\bmod(p-1) $ 是一個排列 $ {\mathbb Z_{p-1}}^* $ （自從 $ a $ 有一個乘法逆）。如果遵循如果 $ b $ 在集合上是均勻隨機的 $ {\mathbb Z_{p-1}}^* $ ， 然後 $ x $ 是。
因此，沒有了解任何資訊 $ \scr F_a $ ，因此關於 $ a $ ，從任意數量的 $ x_j $ 沒有相應的披露 $ b_j $ （假設獨立且均勻隨機 $ {\mathbb Z_{p-1}}^* $ )，無論參數大小或對手的計算能力如何。