整數因式分解

Question

任何人都可以向我解釋爲什麼下面的算法是一個無錯整數因子分解方法，總是返回一個非平凡的因子N. 我知道這聽起來有多奇怪，但我在2年前設計了這種方法，仍然不理解背後的數學邏輯，這使我很難改進它。它非常簡單，只涉及加減運算。

public static long factorX(long N) 
{ 
    long x=0, y=0; 
    long b = (long)(Math.sqrt(N)); 
    long a = b*(b+1)-N; 
    if(a==b) return a; 

    while (a!= 0) 
    { 
     a-= (2+2*x++ - y); 
     if(a<0) { a+= (x+b+1); y++; } 
    } 

return (x+b+1); 
} 

看來，上述方法實際上發現通過迭代不定方程的解決方案：

f(x,y) = a - x(x+1) + (x+b+1)y 
where b = floor(sqrt(N)) and a = b(b+1) - N 
that is, when a = 0, f(x,y) = 0 and (x+b+1) is a factor of N. 

Example: N = 8509 
b = 92, a = 47 
f(34,9) = 47 - 34(34+1) + 9(34+92+1) = 0 
and so x+b+1 = 127 is a factor of N. 

重寫方法：

public static long factorX(long N) 
{ 
long x=1, y=0, f=1; 
long b = (long)(Math.sqrt(N)); 
long a = b*(b+1)-N; 
if(a==b) return a; 

    while(f != 0) 
    { 
    f = a - x*(x+1) + (x+b+1)*y; 
     if(f < 0) y++; 
    x++; 
    } 

return x+b+1; 
} 

我真的很感激上的任何建議如何改進這種方法。

下面是10 18位隨機半素數的列表：

349752871155505651 = 666524689 x 524741059 in 322 ms 
259160452058194903 = 598230151 x 433211953 in 404 ms 
339850094323758691 = 764567807 x 444499613 in 1037 ms 
244246972999490723 = 606170657 x 402934339 in 560 ms 
285622950750261931 = 576888113 x 495109787 in 174 ms 
191975635567268981 = 463688299 x 414018719 in 101 ms 
207216185150553571 = 628978741 x 329448631 in 1029 ms 
224869951114090657 = 675730721 x 332780417 in 1165 ms 
315886983148626037 = 590221057 x 535201141 in 110 ms 
810807767237895131 = 957028363 x 847213937 in 226 ms 
469066333624309021 = 863917189 x 542952889 in 914 ms 

Answer 1

OK，我用Matlab來看看發生了什麼事情在這裏。下面是N = 100000的結果： 您在每次迭代增加x和a變的有趣圖案與其餘N % x+b+1密切相關的（你可以在劇情，a + (N % (x+b+1)) - x = floor(sqrt(N))的灰線看）。 因此，我覺得你只是找到第一個因素通過簡單的迭代比sqrt(N)大，但有一個相當模糊的標準來決定它確實是一個因素：d （對不起，半答案......我要離開，我也許會在以後繼續）。

這裏是MATLAB代碼，以防萬一你想要自行測試：

clear all 
close all 

N = int64(100000); 

histx = []; 
histDiffA = []; 
histy = []; 
hista = []; 
histMod = []; 
histb = []; 

x=int64(0); 
y=int64(0); 
b = int64(floor(sqrt(double(N)))); 
a = int64(b*(b+1)-N); 
if(a==b) 
    factor = a; 
else 
    while (a ~= 0) 
     a = a - (2+2*x - y); 
     histDiffA(end+1) = (2+2*x - y); 
     x = x+1; 
     if(a<0) 
      a = a + (x+b+1); 
      y = y+1; 
     end 
     hista(end+1) = a; 
     histb(end+1) = b; 
     histx(end+1) = x; 
     histy(end+1) = y; 
     histMod(end+1) = mod(N,(x+b+1)); 
    end 
    factor = x+b+1; 
end 

figure('Name', 'Values'); 
hold on 
    plot(hista,'-or') 
    plot(hista+histMod-histx,'--*', 'Color', [0.7 0.7 0.7]) 
    plot(histb,'-ob') 
    plot(histx,'-*g') 
    plot(histy,'-*y') 
    legend({'a', 'a+mod(N,x+b+1)-x', 'b', 'x', 'y'}); % 'Input', 
hold off 

fprintf('factor is %d \n', factor); 

Answer 2

你的方法（NA）的試驗乘法的變體*（N + B），其中n = floor（sqrt（N））和b == 1。

然後，該算法迭代A--/B ++直到的差（NA）*（N + B） - N == 0

局部差異（在相對於a和b）是在分別與2b和2a成比例。因此不需要真正的乘法。

複雜度是| a |的線性函數，或| b | - N越「平方」，該方法收斂得越快。總之，有更快的方法，最容易理解的是二次剩餘篩。

Answer 3

請原諒我的c＃，我不知道Java。 將x和y乘以2會提高算法速度。

using System.Numerics;      // needed for BigInteger 
 
    /* Methods ************************************************************/ 
 
    private static BigInteger sfactor(BigInteger k) // factor odd integers 
 
    { 
 
     BigInteger x, y; 
 
     int flag; 
 
     x = y = iSqrt(k);     // Integer Square Root 
 
     if (x % 2 == 0) { x -= 1; y += 1; } // if even make x & y odd 
 
     do 
 
     { 
 
      flag = BigInteger.Compare((x*y), k); 
 
      if (flag > 0) x -= 2; 
 
      y += 2; 
 
     } while(flag != 0); 
 
     return x;       // return x 
 
    } // end of sfactor() 
 

 
    // Finds the integer square root of a positive number 
 
    private static BigInteger iSqrt(BigInteger num) 
 
    { 
 
     if (0 == num) { return 0; }   // Avoid zero divide 
 
     BigInteger n = (num/2) + 1;   // Initial estimate, never low 
 
     BigInteger n1 = (n + (num/n)) >> 1; // right shift to divide by 2 
 
     while (n1 < n) 
 
     { 
 
      n = n1; 
 
      n1 = (n + (num/n)) >> 1;  // right shift to divide by 2 
 
     } 
 
     return n; 
 
    } // end iSqrt()