對不起，很長的延遲迴到這。正如我在第一個回答中所提到的，我是C++的新手，這在我過度使用全局變量，過度使用BigInteger和BigUnsigned，其他類型可能更好，缺少錯誤檢查和其他編程習慣顯示技術人員可能無法展示的內容。這就是說，讓我解釋我做了什麼，然後會發布代碼。
我在第二個答案中這樣做，因爲第一個答案作爲一個非常簡單的演示非常有用，一旦您瞭解它的作用，Pollard的Rho算法將如何實施。它的作用是先取2個變量，稱它們爲x和y，然後將它們的起始值賦值爲2.然後它通過一個函數運行x，通常爲（x^2 + 1）％n，其中n是你的數字想要因素。它每個週期運行兩次相同的函數。然後計算x和y之間的差值，最後找到這個差值和n的最大公約數。如果這個數字是1，那麼你再次運行x和y。
繼續這個過程，直到GCD不是1或直到x和y再次相等。如果發現GCD不是1，那麼該GCD是n的非平凡因子。如果x和y相等，則（x^2 + 1）％n函數失敗。在這種情況下，您應該再次嘗試使用另一個函數，也許（x^2 + 2）％n等等。
這裏是一個例子。以35，我們知道主要因素是5和7.我會穿過波拉德Rho，並告訴你它是如何找到一個不平凡的因素。循環＃1：X從2開始。然後使用函數（x^2 + 1）％n，（2^2 + 1）％35，我們對x得到5。 Y也從2開始，在函數運行一次後，它的值也是5.但是y總是經過兩次函數，所以第二次運行是（5^2 + 1）％35或26。 x和y之間的差值是21. 21（差值）和35（n）的GCD值是7.我們已經找到了35的主因子！請注意，任何2個數的GCD，甚至是非常大的指數，都可以通過使用Euclid算法的公式快速找到，這就是我將在此處發佈的程序的功能。
關於GCD函數的主題，我使用了一個我爲該程序下載的庫，一個允許使用BigIntegers和BigUnsigned的庫。該庫還內置了GCD功能，我可以使用它。但是我決定留下手寫的GCD功能來達到教學目的。如果你想提高程序的執行時間，使用庫的GCD函數可能是一個好主意，因爲有比Euclid更快的方法，並且可以編寫庫來使用其中一種更快的方法。
另一方面的說明。 .Net 4.5庫也支持使用BigInteger和BigUnsigned。我決定不在這個程序中使用它，因爲我想用C++而不是C++/CLI編寫整個程序。你可以從.Net庫中獲得更好的性能，或者你可能不會。我不知道，但我想分享這也是一種選擇。
我在這裏跳了一下，現在讓我從廣泛的筆觸開始解釋程序的功能，最後我將解釋如何在計算機上設置它，如果您使用Visual Studio 11（也稱爲Visual Studio 2012）。
該程序分配3個數組用於存儲您給它處理的任何數字的因子。這些陣列的寬度爲1000個元素，可能過多，但它可以確保1000個素數因子或更少的任何數字都適合。
當您在提示中輸入數字時，它會假定數字是合成的，並將其放入compositeFactors數組的第一個元素中。然後它經歷了一些公認效率低下的循環，這些循環使用Miller-Rabin來檢查數字是否合成。注意這個測試可以說一個數字是100％置信度的複合數字，也可以說這個數字是非常高的（但不是100％）置信度。信心可以通過程序中的變量confidenceFactor進行調整。程序將檢查2和confidenceFactor之間的每個值（包括），因此比confidenceFactor自身的值少一個總檢查。
我對confidenceFactor的設置是101，它執行100次檢查。如果它表示一個數字是主數字，那麼它真正合成的可能性是4^100中的1，或者與連續200次正確調用公平硬幣翻轉的可能性相同。簡而言之，如果它說這個數字是素數，它可能是，但可以增加confidenceFactor數來獲得更高的置信度。
這裏可能是一個很好的地方，任何提及的是，雖然Pollard的Rho算法可以非常有效地分解較長的long long類型的數目，但Miller-Rabin測試看看一個數字是否合成會更多或更少沒有BigInteger和BigUnsigned類型就沒用了。 BigInteger庫是一個能夠將大數字可靠地分解到它們的主要因素的要求。
當Miller Rabin說這個因子是複合因子時，它是因子，因子存儲在一個臨時數組中，而複合數組中的原始因子除以相同的因子。當數字被識別爲可能的素數時，它們被移入素數因子數組並輸出到屏幕。這個過程一直持續到沒有複合因素。這些因素傾向於按升序排列，但這是巧合。程序不會按升序列出它們，但只會在找到它們時列出它們。
請注意，我無法找到任何函數（x^2 + c）％n，它將對數字4進行分解，無論我給出了什麼值c。 Pollard Rho似乎對所有完美的方格都非常困難，但是4是我發現的唯一合成編號，它完全不受使用所描述格式函數的影響。因此，我在pollard方法中添加了一個4的n，如果是的話，立即返回2。
所以要設置這個程序，這裏是你應該做的。轉到https://mattmccutchen.net/bigint/並下載bigint-2010.04.30.zip。解壓縮並將所有.hh文件和所有C++源文件放入〜\ Program Files \ Microsoft Visual Studio 11.0 \ VC \ include目錄中，但不包括Sample和C++ TestSuite源文件。然後在Visual Studio中創建一個空的項目。在解決方案資源管理器中，右鍵單擊資源文件文件夾並選擇添加...現有項目。在我剛剛提到的目錄中添加所有C++源文件。然後在解決方案expolorer中，右鍵單擊Source Files文件夾並添加一個新項目，選擇C++文件，命名它，然後將下面的源代碼粘貼到它中，它應該適用於您。
不要恭維太多，但是Stack Overflow的人們對C++的瞭解比我更多，如果他們修改我的代碼以使其更好，那太棒了。但即使不是這樣，代碼也是按原樣運作的，它應該有助於說明以編程方式查找中等數字的主要因素所涉及的原則。它不會威脅到通用數字篩選器，但它可以在相當短的時間內對12-14位數的素數進行因子分解，即使是在我使用的舊Core2 Duo計算機上也是如此。
代碼如下。祝你好運。
#include <string>
#include <stdio.h>
#include <iostream>
#include "BigIntegerLibrary.hh"
typedef BigInteger BI;
typedef BigUnsigned BU;
using std::string;
using std::cin;
using std::cout;
BU pollard(BU numberToFactor);
BU gcda(BU differenceBetweenCongruentFunctions, BU numberToFactor);
BU f(BU x, BU numberToFactor, int increment);
void initializeArrays();
BU getNumberToFactor();
void factorComposites();
bool testForComposite (BU num);
BU primeFactors[1000];
BU compositeFactors[1000];
BU tempFactors [1000];
int primeIndex;
int compositeIndex;
int tempIndex;
int numberOfCompositeFactors;
bool allJTestsShowComposite;
int main()
{
while(1)
{
primeIndex=0;
compositeIndex=0;
tempIndex=0;
initializeArrays();
compositeFactors[0] = getNumberToFactor();
cout<<"\n\n";
if (compositeFactors[0] == 0) return 0;
numberOfCompositeFactors = 1;
factorComposites();
}
}
void initializeArrays()
{
for (int i = 0; i<1000;i++)
{
primeFactors[i] = 0;
compositeFactors[i]=0;
tempFactors[i]=0;
}
}
BU getNumberToFactor()
{
std::string s;
std::cout<<"Enter the number for which you want a prime factor, or 0 to quit: ";
std::cin>>s;
return stringToBigUnsigned(s);
}
void factorComposites()
{
while (numberOfCompositeFactors!=0)
{
compositeIndex = 0;
tempIndex = 0;
// This while loop finds non-zero values in compositeFactors.
// If they are composite, it factors them and puts one factor in tempFactors,
// then divides the element in compositeFactors by the same amount.
// If the element is prime, it moves it into tempFactors (zeros the element in compositeFactors)
while (compositeIndex < 1000)
{
if(compositeFactors[compositeIndex] == 0)
{
compositeIndex++;
continue;
}
if(testForComposite(compositeFactors[compositeIndex]) == false)
{
tempFactors[tempIndex] = compositeFactors[compositeIndex];
compositeFactors[compositeIndex] = 0;
tempIndex++;
compositeIndex++;
}
else
{
tempFactors[tempIndex] = pollard (compositeFactors[compositeIndex]);
compositeFactors[compositeIndex] /= tempFactors[tempIndex];
tempIndex++;
compositeIndex++;
}
}
compositeIndex = 0;
// This while loop moves all remaining non-zero values from compositeFactors into tempFactors
// When it is done, compositeFactors should be all 0 value elements
while (compositeIndex < 1000)
{
if (compositeFactors[compositeIndex] != 0)
{
tempFactors[tempIndex] = compositeFactors[compositeIndex];
compositeFactors[compositeIndex] = 0;
tempIndex++;
compositeIndex++;
}
else compositeIndex++;
}
compositeIndex = 0;
tempIndex = 0;
// This while loop checks all non-zero elements in tempIndex.
// Those that are prime are shown on screen and moved to primeFactors
// Those that are composite are moved to compositeFactors
// When this is done, all elements in tempFactors should be 0
while (tempIndex<1000)
{
if(tempFactors[tempIndex] == 0)
{
tempIndex++;
continue;
}
if(testForComposite(tempFactors[tempIndex]) == false)
{
primeFactors[primeIndex] = tempFactors[tempIndex];
cout<<primeFactors[primeIndex]<<"\n";
tempFactors[tempIndex]=0;
primeIndex++;
tempIndex++;
}
else
{
compositeFactors[compositeIndex] = tempFactors[tempIndex];
tempFactors[tempIndex]=0;
compositeIndex++;
tempIndex++;
}
}
compositeIndex=0;
numberOfCompositeFactors=0;
// This while loop just checks to be sure there are still one or more composite factors.
// As long as there are, the outer while loop will repeat
while(compositeIndex<1000)
{
if(compositeFactors[compositeIndex]!=0) numberOfCompositeFactors++;
compositeIndex ++;
}
}
return;
}
// The following method uses the Miller-Rabin primality test to prove with 100% confidence a given number is composite,
// or to establish with a high level of confidence -- but not 100% -- that it is prime
bool testForComposite (BU num)
{
BU confidenceFactor = 101;
if (confidenceFactor >= num) confidenceFactor = num-1;
BU a,d,s, nMinusOne;
nMinusOne=num-1;
d=nMinusOne;
s=0;
while(modexp(d,1,2)==0)
{
d /= 2;
s++;
}
allJTestsShowComposite = true; // assume composite here until we can prove otherwise
for (BI i = 2 ; i<=confidenceFactor;i++)
{
if (modexp(i,d,num) == 1)
continue; // if this modulus is 1, then we cannot prove that num is composite with this value of i, so continue
if (modexp(i,d,num) == nMinusOne)
{
allJTestsShowComposite = false;
continue;
}
BU exponent(1);
for (BU j(0); j.toInt()<=s.toInt()-1;j++)
{
exponent *= 2;
if (modexp(i,exponent*d,num) == nMinusOne)
{
// if the modulus is not right for even a single j, then break and increment i.
allJTestsShowComposite = false;
continue;
}
}
if (allJTestsShowComposite == true) return true; // proven composite with 100% certainty, no need to continue testing
}
return false;
/* not proven composite in any test, so assume prime with a possibility of error =
(1/4)^(number of different values of i tested). This will be equal to the value of the
confidenceFactor variable, and the "witnesses" to the primality of the number being tested will be all integers from
2 through the value of confidenceFactor.
Note that this makes this primality test cryptographically less secure than it could be. It is theoretically possible,
if difficult, for a malicious party to pass a known composite number for which all of the lowest n integers fail to
detect that it is composite. A safer way is to generate random integers in the outer "for" loop and use those in place of
the variable i. Better still if those random numbers are checked to ensure no duplicates are generated.
*/
}
BU pollard(BU n)
{
if (n == 4) return 2;
BU x = 2;
BU y = 2;
BU d = 1;
int increment = 1;
while(d==1||d==n||d==0)
{
x = f(x,n, increment);
y = f(y,n, increment);
y = f(y,n, increment);
if (y>x)
{
d = gcda(y-x, n);
}
else
{
d = gcda(x-y, n);
}
if (d==0)
{
x = 2;
y = 2;
d = 1;
increment++; // This changes the pseudorandom function we use to increment x and y
}
}
return d;
}
BU gcda(BU a, BU b)
{
if (a==b||a==0)
return 0; // If x==y or if the absolute value of (x-y) == the number to be factored, then we have failed to find
// a factor. I think this is not proof of primality, so the process could be repeated with a new function.
// For example, by replacing x*x+1 with x*x+2, and so on. If many such functions fail, primality is likely.
BU currentGCD = 1;
while (currentGCD!=0) // This while loop is based on Euclid's algorithm
{
currentGCD = b % a;
b=a;
a=currentGCD;
}
return b;
}
BU f(BU x, BU n, int increment)
{
return (x * x + increment) % n;
}
不確定是否導致問題，但#define f（x）看起來很奇怪。嘗試添加（（x）*（x）-1）括號以避免宏中的運算符優先級問題。 –