如果有一個算法A可以計算輸入n的模平方根，如何使用它來獲得素因數？
假設給你一個算法 $ A $ 這需要 $ y \in {0, 1, \ldots , N − 1} $ 作為輸入和輸出 $ x \in {0,1,\ldots,N − 1} $ 這樣 $ x^2 \equiv y \pmod{N} $ . 設計一個有效的隨機程序，使用 $ A $ 得到質因數。
這是研究生算法課程的作業問題。
它類似於這個問題。不同之處在於我們沒有具體的數字
51733469。我的想法是我們可以隨機選擇一個數字 $ a $ 之間 $ [1,n-1] $ ， 利用 $ A $ 計算它的模平方根並完全像這裡的解決方案？或者隨機挑選的號碼 $ a $ 應該滿足什麼條件？
方程有多少解 $ x^2\equiv y\pmod N $ ?
這個問題更容易當 $ N $ 是奇怪的並且 $ \gcd(y,N)=1 $ （請注意，當任何一個都不成立時，我們有一個因數 $ N $ ）：有 $ 0 $ 或者 $ 2^k $ 解決方案，其中 $ k $ 是不同素數的數量 $ p_i $ 劃分 $ N $ . 證明開始於 $ N $ 素數（見勒讓德符號），然後是素數的冪，然後是不同素數的冪的乘積（使用中國剩餘定理）。
為什麼算法 $ A $ 總是返回相同的輸出？
被認為可以回答問題的證明應該有效，包括算法何時 $ A $ 總是返回相同的輸出 $ x $ 用於輸入 $ (y,N) $ ，因為問題的假設“假設..”中沒有任何內容表明 $ A $ 將返回所有解決方案，或者在重複呼叫時最終返回所有解決方案。許多算法是確定性的，即總是對給定的輸入執行相同的操作，包括產生相同的結果。實際上，在密碼學中，考慮到隨機行為必須來自顯式的額外隨機輸入，我們經常隱含地限制這種確定性算法。
提示：您希望有兩種解決方案：一種是您事先知道的，另一種是算法會給您的。該算法無法讀懂您的想法，因此它有可能返回另一個解決方案，也許這會有所幫助。