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

TABLE 12.1

s = square root of n

n (n+1)/2-s

101 10.04987562 40.95012438

1001 31.63858404 469.361416

10001 100.0049999 4900.995

100001 316.2293472 49684.77065

1000001 1000.0005 499000.9995

10000001 3162.277818 4996838.722

100000001 10000.00005 49990001

1000000001 31622.77662 499968378.2

10000000001 100000 4999900001

are close together (thereby making x and y close together). This keeps the search of the
sequence

2

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

relatively short.

Java Algorithm To develop a method to extract factors of n using Fermat factorization,

we need to be able to compute . The BigInteger class contains no square root method, so

we must write our own. We wish this method to return the largest integer whose square
does not exceed

√ n

. To compute the integer square root of a positive number, we will approach
the real root using a numerical algorithm known as Newton's method. Suppose we wish to
find the square root of

n

n ; i.e., a solution to

x

2 = n .

We will do this by trying to find a root (or a zero) of the function

2

.
To use Newton's method, we need the derivative of f ( x ), which, in this case is

f ( x ) = x n

.
We begin with an initial guess for the root, say

f ( x ) = 2 x

r 0 . Suppose, for convenience, that this
guess overestimates the true root. (See Figure 12.1.) We compute subsequent guesses by com-
puting

r k = r k 1 f ( r k 1 )/ f ( r k 1 ) k = 1, 2, 3, . . .

) rather quickly. If the root we seek is irrational,
we truncate the result to produce the integer square root. I have written a sqrt() method and

These guesses approach a true root of f ( x