A better algorithm for factoring odd positive integers is Fermat's factorization algorithm.
(a) Let n=ab be an odd composite number. Prove that n can be written as the difference of two perfect squares:
n=x2−y2=(x−y)(x+y).
Consequently, a positive odd integer can be factored exactly when we can find integers x and y such that n=x2−y2.
(b) Write a program to implement the following factorization algorithm based on the observation in part (a). The expression ceiling(sqrt(n)) means the smallest integer greater than or equal to the square root of n. Write another program to do factorization using trial division and compare the speed of the two algorithms. Which algorithm is faster and why?
\begin{verbatim}
x := ceiling(sqrt(n))
y := 1
1 : while x^2 - y^2 > n do
y := y + 1
if x^2 - y^2 < n then
x := x + 1
y := 1
goto 1
else if x^2 - y^2 = 0 then
a := x - y
b := x + y
write n = a * b
\end{verbatim}