從隱藏函式中提取模數
我有一個隱藏功能 $ f(x) = x \pmod{n} $ 並想解決 $ n $ 基於一組可以自由選擇的輸入和輸出對。
我想在沒有蠻力的情況下做到這一點（即從 $ x_0=1 $ 並迭代 $ x_{i+1}=x_i+1 $ 直到 $ f(x_i)=0 $ ).
到目前為止，我觀察到，如果我擴展 $ x=an+b $ ，然後減去 $ f(x)=b $ 從輸入中，我剩下 $ x-f(x)=an $ .
我可以對各種輸入重複此操作並獲得不同倍數的列表 $ n $ ，但我不知道如何使用它們來解決 $ n $ 本身。
如果我使用上述程序獲得不同的 $ a_0n $ 和 $ a_1n $ , 我可以計算 $ gcd(a_0n,,a_1n) = kn $ , 但不能保證 $ k=1 $ ，無論有多少情況都是一樣的 $ a_in $ 以這種方式處理。
這甚至是一個可解決的問題，還是我需要在函式上包含額外的約束，比如明確說明域，也許 $ f := \mathbb{F_2}[x] \to \mathbb{F_2}[x] $ （具有二進制係數的多項式）？
你已經完成了艱苦的工作，發現你可以獲得 $ m_i=a_i,n $ 對於各種（未知但基本上是隨機的）值 $ a_i $ .
現在定義 $ n_0=m_0 $ , 併計算 $ n_i=\gcd(n_{i-1},m_i) $ 為增加 $ i>0 $ . 越早越好， $ n_i $ 會收斂到 $ n $ .
這可以嚴格證明（儘管我們經常在加密環境中跳過嚴格的證明）。草圖：通過歸納證明 $ n_i=k_i,n $ 為了 $ k_i $ 劃分所有 $ a_j $ 和 $ 0\le j\le i $ . 然後考慮任何主要因素 $ p $ 的 $ k_i $ ，以及它存活到 $ i $ 在假設 $ a_i $ 是隨機的。
注意：通過將“素數”更改為“不可約”，這適用於比整數更廣泛的上下文，例如多項式。