如果有一個算法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 $ 將返回所有解決方案,或者在重複呼叫時最終返回所有解決方案。許多算法是確定性的,即總是對給定的輸入執行相同的操作,包括產生相同的結果。實際上,在密碼學中,考慮到隨機行為必須來自顯式的額外隨機輸入,我們經常隱含地限制這種確定性算法。
提示:您希望有兩種解決方案:一種是您事先知道的,另一種是算法會給您的。該算法無法讀懂您的想法,因此它有可能返回另一個解決方案,也許這會有所幫助。