Fermat's Method

This 400-yr old method is the basis for many modern sieving factorization methods.
It relies on the discovery of an expression for the input number, as the difference between two (integral) squares.

http://en.wikipedia.org/wiki/Fermat%27s_factorization_method

Also, the pseudocode immediately below is taken from a PD document by Connelly Barnes of Oregon State University
http://oregonstate.edu/~barnesc/documents/factoring.pdf

function fermatFactor(N)
for x from ceil(sqrt(N)) to N
ySquared := x * x - N
if isSquare(ySquared) then
y := sqrt(ySquared)
s := (x - y)
t := (x + y)
if s <> 1 and s <> N then
return s, t
end if
end if
end for
end function

And here is its Java implementation (from superfac9) [with thanks to DT]:

BigInteger factorizefermat(BigInteger n) {
BigInteger a, bSq;
long iterations = 1L;

a = sqrt(n);
if(n.mod(a).compareTo(ZERO) == 0) return a;

while(iterations<10000000) {
bSq = a.multiply(a).subtract(n);
if(fastsquareQ(bSq))
return a.subtract(sqrt(bSq)); // bSq is a square, factorization found
a = a.add(ONE);
iterations++;
}

return n;
}