Every positive odd integer can be represented in the form by writing (with ) and noting that this gives

(2)

(3)

Adding and subtracting,

(4)

(5)

so solving for and gives

(6)

(7)

Therefore,

(8)

As the first trial for , try , where is the ceiling function.
Then check if

(9)

is a square number. There are only 22 combinations of the last two digits which a square number can
assume, so most combinations can be eliminated. If is not a square number,
then try

(10)

so

(11)

(12)

(13)

(14)

Continue with

(15)

(16)

(17)

(18)

(19)

so subsequent differences are obtained simply by adding two.

Maurice Kraitchik sped up the algorithm by looking for
and
satisfying

(20)

i.e., .
This congruence has uninteresting solutions and interesting solutions . It turns out that if is odd and divisible
by at least two different primes, then at least half
of the solutions to with relatively prime to
are interesting. For such solutions, is neither nor 1 and is therefore a nontrivial factor of (Pomerance 1996). This algorithm
can be used to prove primality, but is not practical. In 1931, Lehmer and Powers
discovered how to search for such pairs using continued
fractions. This method was improved by Morrison and Brillhart (1975) into the
continued fraction factorization
algorithm, which was the fastest algorithm in use
before the quadratic sieve factorization method
was developed.

Lehmer, D. H. and Powers, R. E. "On Factoring Large Numbers." Bull. Amer. Math. Soc.37, 770-776, 1931.McKee,
J. "Speeding Fermat's Factoring Method." Math. Comput.68,
1729-1738, 1999.Morrison, M. A. and Brillhart, J. "A Method
of Factoring and the Factorization of ." Math. Comput.29, 183-205, 1975.Pomerance,
C. "A Tale of Two Sieves." Not. Amer. Math. Soc.43, 1473-1485,
1996.