java - Integer Factorization -

java - Integer Factorization -

could explain me why algorithm below error-free integer factorization method homecoming non-trivial factor of n. know how weird sounds, designed method 2 years ago , still don't understand mathematical logic behind it, making hard me improve it. it's simple involves add-on , subtraction.

public static long factorx( long n ) { long x=0, y=0; long b = (long)(math.sqrt(n)); long = b*(b+1)-n; if( a==b ) homecoming a; while ( a!= 0 ) { a-= ( 2+2*x++ - y); if( a<0 ) { a+= (x+b+1); y++; } } homecoming ( x+b+1 ); }

it seems above method finds solution iteration diophantine equation:

f(x,y) = - x(x+1) + (x+b+1)y b = floor( sqrt(n) ) , = b(b+1) - n is, when = 0, f(x,y) = 0 , (x+b+1) factor of n. example: n = 8509 b = 92, = 47 f(34,9) = 47 - 34(34+1) + 9(34+92+1) = 0 , x+b+1 = 127 factor of n.

rewriting method:

public static long factorx(long n) { long x=1, y=0, f=1; long b = (long)(math.sqrt(n)); long = b*(b+1)-n; if( a==b ) homecoming a; while( f != 0 ) { f = - x*(x+1) + (x+b+1)*y; if( f < 0 ) y++; x++; } homecoming x+b+1; }

i'd appreciate suggestions on how improve method.

here's list of 10 18-digit random semiprimes:

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

ok, used matlab see going here. here result n=100000: increasing x on each iteration, , funny pattern of a variable related remainder n % x+b+1 (as can see in grayness line of plot, a + (n % (x+b+1)) - x = floor(sqrt(n))). thus, i think finding first factor larger sqrt(n) simple iteration, rather obscure criterion decide factor :d (sorry half-answer... have leave, maybe go on later).

here matlab code, in case want test yourself:

clear close n = int64(100000); histx = []; histdiffa = []; histy = []; hista = []; histmod = []; histb = []; x=int64(0); y=int64(0); b = int64(floor(sqrt(double(n)))); = int64(b*(b+1)-n); if( a==b ) factor = a; else while ( ~= 0 ) = - ( 2+2*x - y); histdiffa(end+1) = ( 2+2*x - y); x = x+1; if( a<0 ) = + (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 %d \n', factor );

java