Integer Factorization
<p>Could anyone explain to me why the algorithm below is an error-free integer factorization method that always return a non-trivial factor of N.
I know how weird this sounds, but I designed this method 2 years ago and still don't understand the mathematical logic behind it, which is making it difficult for me to improve it. It's so simple that it involves only addition and subtraction.</p>

<pre><code>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&lt;0 ) { a+= (x+b+1); y++; }
    }

return ( x+b+1 );
}
</code></pre>

<p>It seems that the above method actually finds a solution by iteration to the diophantine equation:</p>

<pre><code>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.  
</code></pre>

<p>Rewriting the method:</p>

<pre><code>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 &lt; 0 ) y++;
    x++;
  }

return x+b+1;
}  
</code></pre>

<p>I'd really appreciate any suggestions on how to improve this method.</p>

<p>Here's a list of 10 18-digit random semiprimes:</p>

<pre><code>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
</code></pre>
