Saturday, August 18, 2007
JSH: Perfect factoring algorithm
Algorithm for guaranteeing the factorization of a target composite T of any size.
Use (x+k)^2 = y^2 + 2k^2 + n*T.
Use (x+k)^2 = y^2 + 2k^2 + n*T.
- Pick k=2 and an n that gives you an absolute value of 2k^2 + n*T above the minimums, where you can choose
abs(2k^2 + n*T)> 2x_res*T where
x_res = k*(2)^{-1} mod T
and solve for x and y by factoring 2k^2 + n*T, iterating through integer combinations to check with all possible values for integer x and y. - If your first n does not factor non-trivially increment its absolute value by 1 and try again, and do this for a maximum of 3 increments and you are guaranteed to factor T without regard to the size of T.
# posted by James Harris @ 21:19 
