Fermat Factoring by difference of squares
A classical algorithm for factoring a positive integer z is to find two squares, t^2 and s^2, such that t^2 - s^2 = z. 65 = 5 * 13 65 = ((13+5)/2)^2 -((13-5)/2)^2 65 = 9^2 - 4^2 65 = 81 - 16 If z = x y if and only if z = ((y+x)/2) )^2 - ((y-x)/2)^2 z = t^2 - s^2 if and only if z = (t-s)(t+s). To... Sign in to see full entry.