100％確定性的快速素性測試？

我對任意大小的數據類型使用GMP（與MPIR）。我也使用它的素性測試函數，它使用Miller-Rabin方法，但它不準確。這是我想要解決的問題。100％確定性的快速素性測試？

我能夠證實該號碼18446744073709551253是主要使用蠻力，用開方的方法。

是否有任何方法檢查大數是否爲總數，精度達到100％？

它不應該使用太多的內存/存儲空間，只有幾兆字節是可以接受的。
它應該比我使用的sqrt方法更快。
它應該是大小至少爲64位，或較大的數字工作。
最後，它應該是100％準確的，maybes！

我的選擇是什麼？

我可以用蠻力方法（64位數字）住在哪裏，但出於興趣，我想更快&大。另外，64位數字檢查太慢了：總共43秒！

來源

2012-12-11 Rookie

對於數字高達'2^64'，Baillie Pomerance Selfridge Wagstaff測試是可靠的。在此之上，APRCL或橢圓曲線素數證明。 –

你需要100％的準確性嗎？除非你的程序的目的是尋找大的素數（不喜歡不存在這樣做的程序），否則我不會看到任何應用程序無法接受無限小的錯誤機會。 – Grizzly

@Grizzly，我需要它嗎？在我的腦海當然:)如果我在一個程序中做了一個按鈕，它應該告訴我們這個數字是不是一個總數，聽到「也許它是一個總理，我不知道，問別人！」是令人討厭的。：p – Rookie

對於非常大的數字，AKS primality test是一個確定性的素性測試，其運行時間爲O（其中n是感興趣的數量）。這比O（√ n）算法指數地更快。但是，該算法具有較大的常數因子，因此直到您的數字變得相當大時纔是實用的。

希望這會有所幫助！

來源

2012-12-11 22:07:04 templatetypedef

谷歌搜索「AKS GMP」發現一些有趣的討論。 –

那麼，通過使用AKS，我的號碼必須至少有多大？ – Rookie

@ Rookie- AKS將一直工作，但對於小數字可能需要比其他方法更長的時間。我真的不知道它將在64位整數上運行得有多快。 – templatetypedef

作爲一般的點100％的把握是不可能在物理計算機上，因爲有一個小而有限的可能性，即一些部件已經無形中失敗，那在最後給出的答案是不正確的。鑑於這個事實，那麼你可以運行足夠多的Miller-Rabin概率測試，即複合數的概率遠小於硬件失敗的概率。由此不難測試高達1 2^256級確定性：

boolean isPrime(num) 
    limit <- 256 
    certainty <- 0 
    while (certainty < limit) 
    if (millerRabin returns notPrime) 
     return false 
     exit 
    else 
     certainty <- certainty + 2 
    endif 
    endwhile 
    return true 
end isPrime

這將測試數是素數，高達1比2^256是必然的。每個M-R測試的確定性都增加了四倍。我已經看到了所謂的「工業強度素數」的結果素數，足以滿足所有實際目的，但不完全是爲了理論上的數學確定性。

來源

2012-12-12 13:23:04 rossum

對於小ñ，審判庭的作品;極限可能在10^12左右。對於稍大的n，有各種研究（見Gerhard Jaeschke和Zhou Zhang的着作），計算Miller-Rabin鹼基各種集合中最小的僞蛋白;那會帶你到10^25左右。之後，事情變得艱難。

素性證明的「大炮」是APRCL方法（可以稱爲雅可比和或高斯和）和ECPP方法（基於橢圓曲線）。兩者都很複雜，所以你會想找到一個實現，不要寫你自己的。這些方法可以處理數百個數字。

的AKS方法被證明是多項式時間，並且很容易實現，但該比例常數是非常高的，所以它不是在實踐中非常有用。

如果你能因素ñ -1，甚至部分因素是，波克林頓的方法可以確定的ñ素性。波克林頓的方法本身很快，但因素可能不是。

對於所有的這些，你要合理地確定一個數是素數，你試圖證明它。如果你的數字不是素數，所有這些方法都會正確地確定，但首先他們會浪費很多時間來試圖證明一個合數是質數。

我有AKS和Pocklington實現我的博客。

來源

2012-12-12 14:01:31 user448810

證明的方法取決於素數的你正在試圖證明（例如，梅森素數有證明，只有與他們合作素性特殊的方法），並以十進制數字表示的尺寸類型。如果您正在查看數百位數字，那麼只有一個解決方案，儘管不足：AKS算法。對於足夠大的素數而言，它比其他素數證明算法快得多，但當它變得有用時，它會花費很長時間纔會真的不值得麻煩。

素性證明了大的數字仍然是一個尚未完全解決的問題。如果是的話，EFF獎項將全部頒發，加密技術會出現一些問題，而不是用於素數列表，而是用於找到它們的方法。

我相信在不久的將來，將會出現一個證明素性的新算法，它不依賴於預先生成的直到n的平方根的素數列表，並且不會做一個蠻力用於確保平方根下的所有素數（以及許多非素數）用作n的素數的見證。這種新算法可能會取決於數學概念，這些概念比分析數論所使用的概念簡單得多。素數中有模式，這很確定。識別這些模式完全是另一回事。

來源

2012-12-16 07:22:46 Adam

100％確定性的快速素性測試？

回答

相關問題