将数字分解为2个主要辅因子
电报认证的要求之一是将给定数量分解为2个主要因子。 特别是P*Q = N, where N < 2^63
我们怎样才能找到较小的素数因子，使得P < square_root(N)
我的建议：
1）预先计算从3到2^31.5素数，然后测试N mod P = 0
2）找到一个算法来测试质数（但我们仍然需要测试N mod P =0 ）
是否有适合这种情况的素数算法？
啊! 我只是把这个程序放进去，然后意识到你已经标记了你的问题C＃。 这是C ++，我几年前写的Pollard Rho版本，并在此发布，以帮助其他人理解它。 在半因子分解中，它比试验分裂快了许多倍。 正如我所说，我很遗憾它是C ++而不是C＃，但你应该能够理解这个概念，甚至可以轻松地移植它。 作为奖励，.NET库有一个用于处理任意大整数的命名空间，我的C ++实现要求我为它们找到第三方库。 无论如何，即使在C＃中，下面的程序也会在不到1秒的时间内将2 ^ 63次序列的半素数分成2个素数。 甚至比这更快的算法，但它们要复杂得多。
#include #include #include #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<= 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(yx, n); } else { d = gcda(xy, 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 (xy) == 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; }
波拉德的Rho算法[VB.Net]
发现P非常快，其中P*Q = N ，对于N < 2^63
Dim rnd As New System.Random Function PollardRho(n As BigInteger) As BigInteger If n Mod 2 = 0 Then Return 2 Dim x As BigInteger = rnd.Next(1, 1000) Dim c As BigInteger = rnd.Next(1, 1000) Dim g As BigInteger = 1 Dim y = x While g = 1 x = ((x * x) Mod n + c) Mod n y = ((y * y) Mod n + c) Mod n y = ((y * y) Mod n + c) Mod n g = gcd(BigInteger.Abs(x - y), n) End While Return g End Function Function gcd(a As BigInteger, b As BigInteger) As BigInteger Dim r As BigInteger While b <> 0 r = a Mod b a = b b = r End While Return a End Function
理查德布伦特的算法[VB.Net]这更快。
Function Brent(n As BigInteger) As BigInteger If n Mod 2 = 0 Then Return 2 Dim y As BigInteger = rnd.Next(1, 1000) Dim c As BigInteger = rnd.Next(1, 1000) Dim m As BigInteger = rnd.Next(1, 1000) Dim g As BigInteger = 1 Dim r As BigInteger = 1 Dim q As BigInteger = 1 Dim x As BigInteger = 0 Dim ys As BigInteger = 0 While g = 1 x = y For i = 1 To r y = ((y * y) Mod n + c) Mod n Next Dim k = New BigInteger(0) While (k < r And g = 1) ys = y For i = 1 To BigInteger.Min(m, r - k) y = ((y * y) Mod n + c) Mod n q = q * (BigInteger.Abs(x - y)) Mod n Next g = gcd(q, n) k = k + m End While r = r * 2 End While If g = n Then While True ys = ((ys * ys) Mod n + c) Mod n g = gcd(BigInteger.Abs(x - ys), n) If g > 1 Then Exit While End If End While End If Return g End Function