證明卡邁克爾數的算法
我有一個確定一個數字是否是素數的應用程序,目前我得到一個隨機數,然後進行費馬素數測試以找出該數字是否可能是素數(所以這仍然可以是卡邁克爾數),然後,我使用 Miller-Rabin 算法進行測試,以確定該數字是否可能是素數(有 2^-81 的機率這仍然可以是複合數)。
我的問題是:
- 是否有一種算法可以確定一個數字是否是卡邁克爾數(確定性與否)
- 證明費馬素數檢驗並且數字不是卡邁克爾數是否足以證明該數字是實素數
嗯,是的,有一個機率多項式時間算法確定一個數字是否是卡邁克爾數(機率在它總是返回正確值的意義上,它以高機率快速終止)。但是,它並不像您為您的應用程序考慮的那麼有用。
該算法基於兩個觀察結果:
- 卡邁克爾數很容易分解
- 給定完整的因式分解,很容易驗證一個數字是否是 Carmichael 數(Korselt 的標準,正如 Thomas 所提到的)。
這是第一個觀察的細節:如果我們有一個合數 $ N $ , 和一個偶數 $ e $ 為此 $ x^e \equiv 1 \bmod N $ 對於值的重要部分 $ x $ ,那麼我們可以分解 $ N $ . 我們通過計算來做到這一點 $ \lambda $ 2 的冪,使得 $ e/\lambda $ 是奇數,對於隨機值 $ x $ , 計算 $ x^{e/\lambda}, x^{2e/\lambda}, x^{4e/\lambda}, …, x^e $ . 如果系列以 1 結尾(它很有可能會;這就是我們放置的條件 $ e $ ),我們查看第一個 1 之前的值;如果那個值 $ x^{ke/\lambda} $ 不是-1,那麼我們有非平凡因素 $ gcd(N, x^{ke/\lambda}-1) $ 和 $ gcd(N, x^{ke/\lambda}+1) $ (因為 $ x^{ke/\lambda} $ 是 1) 的非平凡平方根。此外,如果 $ N $ 有超過 2 個因子,這會產生一個隨機因子分解 $ N $ .
現在,如果 $ N $ 是一個卡邁克爾數,那麼 $ e = N-1 $ 是這樣一個值;事實上,對於任何 $ x $ , 我們有 $ gcd(x,N)>1 $ (因此我們有一個因式分解 $ N $ ), 或者 $ x^{e} \equiv 1 $ (因此我們有一個很好的機率分解)。此外,如果我們選擇一個值 $ x $ 我們發現 $ gcd(x,N)=1 $ 和 $ x^{e} \neq 1 $ ,那麼我們剛剛證明了 $ N $ 不是卡邁克爾數。
因此,機率算法看起來像:
檢查是否 $ N $ 是素數;如果是,則返回 FALSE。
雖然我們沒有完整的因式分解 $ N $
- 隨機選擇 $ x $
- 如果 $ gcd(x, N)=1 $ 和 $ x^{N-1} \ne 1 \bmod N $ ,然後返回 FALSE。
- 否則檢查 $ gcd(x, N) $ , $ x^{(N-1)/\lambda} $ 對於非平凡分解 $ N $
- 如果我們找到了一個非平凡因子,則使用該非平凡因子來嘗試找到更多的素因子 $ N $
一旦我們有一個完整的因式分解 $ N $ , 應用 Korselt 的標準來確定是否 $ N $ 是卡邁克爾數。
這回答了你的問題,但是它對於確定一個數字是否是素數並不是很有用。
另一方面,如果您需要一種產生大素數的算法,並且您對機率方法不滿意,您是否考慮過 Shawe-Taylor 算法附錄 A.1.2.1?該算法生成的數字保證是素數,我的經驗是它與使用 Miller-Rabin 測試搜尋素數一樣快。