卡邁克爾數因式分解

不確定這是否是這個問題的正確論壇，值得一試。

我面臨的任務是實現一個多時間算法，該算法找到一個卡邁克爾數的非平凡因子。網路上的許多資源表明這很容易，但是，沒有進一步解釋為什麼會這樣？

此外，由於當找到非平凡平方根 1 時，miller-rabbin 退出，這可用於找到卡邁克爾數的因子： $ x^2 \equiv 1 = (x+1)(x-1)\equiv0\ mod\ N $ ，其中 N 是我們想要分解的卡邁克爾數。因此，必須使用因子來找到 $ \gcd(x+1,N) $ 和 $ \gcd(x-1, N) $ ， 正確的？

由於強騙子的問題，在某些情況下我們會錯過一些因素，這是一個主要問題嗎？由於 miller-rabbin 測試僅以 1/4 的機率通過複合材料，因此說找到一個因子的機會 > 0.5 是否正確？

親切的問候！

是的，將 Miller-Rabin 與隨機見證人一起使用確實提供了一種實用的分解方法。當您執行 Miller-Rabin 算法時，它可以以以下三種方式之一結束：

1. 最終值不是1；這種情況導致米勒拉賓輸出“複合”
2. 一個中間值不是 1 或 N-1，而是下一個值是 1；這會導致 Miller-Rabin 輸出“複合”
3. 初始值為1；或中間值為N-1；這會導致 Miller-Rabin 輸出“可能是素數”。

情況 1 僅在以下情況下才會發生 $ W^{N-1} \neq 1 \bmod N $ ，然而，我們得到卡邁克爾數的不等式只有當 $ W $ 是一個因數的倍數 $ N $ ; 在這種情況下， $ gcd(W, N) $ 給了我們一個重要的因素。

對於案例 2，這給了我們一個不平凡的價值 $ X $ 為此 $ X^2 = 1 \bmod N $ ; 正如您正確指出的那樣，一個非平凡的平方根 $ N $ 立即給了我們重要的因素 $ gcd(X+1, N), gcd(X-1, N) $

因此，在 Carmichael 數的特定情況下，如果 Miller Rabin 測試輸出“複合”，我們總是有足夠的資訊來立即分解。並且，當給米勒-拉賓一個合數時，它會輸出機率 > 3/4 的“複合”；因此，單次迭代將允許我們以高機率進行因子分解。

事實上，對於 Carmichael 數，Miller Rabin 的成功機率實際上是 > 7/8；對於米勒拉賓來說，卡邁克爾的數字並不是最糟糕的情況。

這為我們提供了一種實用的分解方法；但是出於迂腐的原因，它實際上並沒有回答這個問題。這不是多時間算法；它是一種機率多時間算法，每次迭代都有很好的機率產生一個因子，但它也有可能找不到一個因子。

試試這個（上面評論的描述 - 也寫了同樣的部落格！+ 在 math.stackexchange.com 上發布了同樣的內容）：

對於每個素數基數 (2,3,5,7,11…)，嘗試檢查餘數下的指數

$$ (n-1)/2 $$,$$ (n-1)/4 $$,$$ (n-1)/8 $$…等等。一旦找到除 1 以外的數字，請嘗試： gcd (x-1,n)

或者

gcd (x+1,n)。

應該是導致的因素之一！

例如 ：

Moduluo : n=561 base : a=2

$$ a^(n-1/1) $$模 (n): (2 ^ 560) 模 (561) = 1 $$ a^(n-1/2) $$模 (n): (2 ^ 280) 模 (561) = 1 $$ a^(n-1/4) $$模 (n): (2 ^ 140) 模 (561) = 67 gcd(561,68)=17

gcd(561,66)=33

561/33=17

561=31117 !!

相關連結 ：

http://mathforum.org/kb/message.jspa?messageID=5488111 https://en.wikipedia.org/wiki/Carmichael_number

另請參閱此答案。

引用自：https://crypto.stackexchange.com/questions/5279