Factorization Techniques - Introduction to Cryptography with Java Applets - page 221

To see how it works, consider an odd positive integer n , and suppose that
n = ab

where a and b are integers. (Note that since n is odd, both a and b must be odd.) Now, note
that we can write n as the difference of two squares
n = s 2 t 2

if we have

s = ( a + b )/2, and

t = ( a b )/2.
Note that both s and t are integers, since both a and b are odd. Similarly, if we have an
odd positive integer n that is the difference of two squares, say
n = x 2 y 2

then we can factor this integer into

n = cd

where

c = ( x + y ), and
d = ( x y).

Thus, we can approach the problem of factoring an odd positive integer n by looking for
squares whose difference is n , rather than looking directly for factors of n . That is, we look
for integer solutions of the equation

n = x 2 y 2 .

We can do this by rewriting the previous equation in this way:
y 2 = x 2 n .

and search for perfect squares of the form x 2

n . We can do this sequentially; we start with
m , the smallest integer greater than the square root of n , and look for perfect squares in the
sequence

m 2 n , ( m + 1) 2 n , ( m + 2) 2

n , . . .

This search is guaranteed to end, since m will have to go no further than m = ( n + 1)/2,
since:

(( n + 1)/2) 2 n = (( n 1)/2) 2

and all the terms are integers. To see that the previous equation is true, note that
(( n + 1)/2) 2

(( n 1)/2) 2 = ( n 2 + 2 n + 1)/4 ( n 2

2 n + 1)/4 = 4 n /4 = n .

(However, if we do go this far, note that we have only obtained the trivial factorization
n = n 1.)