如何確定一個令人難以置信的大數是否是質數？

2^7 - 1，2^31 - 1，2^127 - 1，等等。

這不是一個家庭作業問題，我只是在研究質數，很多信息都在我頭上（傅立葉變換）。最初我只是使用這樣的功能：

public static bool IsPrime(int candidate) 
{ 
    if ((candidate & 1) == 0) 
    { 
     return candidate == 2; 
    } 

    for (int i = 3; (i * i) <= candidate; i += 2) 
    { 
     if ((candidate % i) == 0) 
     { 
      return false; 
     } 
    } 

    return candidate != 1; 
}

但是，一旦數字變得太大，停止工作。我也看着Sieve of Eratosthenes，但顯然只適用於小得多的數字。

爲了澄清，我不想寫一個程序找到素數，而是確定一個給定的數字是否爲素數。我正在尋找.NET Framework中的BigInteger結構，如果我能夠編寫足夠高效的算法（我願意花幾天時間完成），它看起來很有希望。

我不確定在這種情況下數學證明是否會更好，但我在這方面沒有太多的知識而不是編程，但如果有證明專門用於這類數字，絕對值得期待。

謝謝。

來源

2011-09-28 Ryan Peschel

維基百科的概要：http://en.wikipedia.org/wiki/Primality_test –

[Mersenne primes]（http://en.wikipedia.org/wiki/Mersenne_prime）也有關於特定形式的信息素數（'2^p-1'） – Mat

尋找大質數是一項持續不斷的科學努力，獲得新獎項。爲了證明一個「令人難以置信的」大數是一個主要數據是超級計算機和數學家團隊的一部分。解決使用運行在每天硬件上的.NET代碼的實際限制與迄今爲止發現的最大的總理相比可能非常低。 –

保號是一個大問題。現代密碼學的基礎很難。

取決於你的號碼的大小......你可以得到所有素數的列表，直到你正在尋找的數字的平方根。這比每次增加2次要少得多。問題在於找到一個很大的列表。如果你的數字是10^100，那麼你需要10^50或更少的所有素數，這仍然是一個巨大的數字。

來源

2011-09-28 20:29:35 corsiKa

確定數字是否爲素數是（可能）比分解它們小的問題。有確定性算法來測試數值數字中多項式的素數，但沒有這種已知的因式分解算法。基本上，你可以證明一個數字是複合的而沒有實際展示其因素，並且證明它是素數而沒有詳盡地檢查所有候選因素。 –

問題不在於保理，而僅僅是檢查一個數字是否爲素數。原始性測試可以在幾千位的素數上高效完成。例如使用概率[Miller-Rabin測試]（http://en.wikipedia.org/wiki/Miller-Rabin_primality_test）。 – CodesInChaos

你的號碼有一些上限嗎？你提到你會安置好幾天。如果是這樣，除非您的號碼非常大，否則您的當前算法將起作用。

你也可以看看Miller–Rabin primality test

來源

2011-09-28 20:28:36 rohit89

'2^127-1'確實很大（當然是主要的，但是你不會證明在幾天內使用提問者的代碼）。 –

您列出的數字：2^7 - 1, 2^31 - 1, 2^127 - 1被稱爲Mersenne Numbers。已經有一整個分佈式計算項目來查找這些項目。它被稱爲GIMPS。

所以你的問題的答案不是微不足道的。所有這些形式的現有已知的素數這裏列出：

http://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes

來源

2011-09-28 20:40:36 Mysticial

我不認爲你會比檢查它是否在已知表格中快得多。 – celion

的Java自帶的概率素性測試之一的實現 - 見java.math.BigInteger.isProbablePrime（）。我認爲這意味着C＃在語言上看起來很像。我沒有找到，但找到一個我在網上找到了一些代碼http://www.codeproject.com/KB/cs/biginteger.aspx。

來源

2011-09-29 04:19:26 mcdowella

如何確定一個令人難以置信的大數是否是質數？

回答

相關問題