The basic Fermat algorithm is as follows:
Assume that n is an odd positive integer. Set c = [√n] (`ceiling of √n '). Then we consider in turn the numbers
c2 - n; (c+1)2 - n; (c+2)2 - n.....
until a perfect square is found. If this occurs at the term (c+k)2 - n, then putting a = c+k we have
a2 - n = (c+k)2 - n = b2;
say, and then n = a2 - b2, as desired.
This process will terminate in the worst case when a = (n+1)/2, since
n = [(n+1)/2]2 - [(n-1)/2]2
In particular, the number of steps taken will be at worst
(n+1)/2 - [√n] +1 = O(n)