Factoring
一般因式分解和單向函式
讓一個函式 $ f $ 是單向的，如果存在一個機率多項式時間算法來找到原像 $ y = f(x) $ 為統一選擇 $ x $ 以不可忽略的機率。
定義函式為 $ f(x,y) = x\times y $ ，其中的值 $ x $ 和 $ y $ 範圍內的整數 $ [2^{n-1}, 2^n-1] $ （基本上，它們是 $ n $ - 最左邊的位設置的位數）。是 $ f $ 單程？？
（雖然收到的機率為 0.75 $ y $ 甚至， $ 2 $ 和 $ y/2 $ 不能作為因素輸出，因為我希望原像位於該特定範圍內）
您想知道的是弱單向函式和強單向函式之間的區別。Google應該給你定義（例如這裡是我找到的第一個連結）。一般輸入的因式分解函式不是一個強大的單向函式，因為有些輸出很容易反轉。但它是一個弱 OWF，因為沒有多時間對手的機率超過 $ 1-1/\mathsf{poly} $ 反轉它（據我們所知）。
此外，即使弱 OWF 通常不是強 OWF，但我們知道從弱 OWF 建構強 OWF 的通用方法——換句話說，兩個假設在形式上是等價的。參見例如這個線上課程，它專門處理您關心的產品功能。