Appendix C: Factoring Large Integers - Codes: The Guide to Secrecy from Ancient to Modern Times - page 510

building a sieve on the prime factors of n , which did not let him predict, for a
given prime p , a different residue to yield a square. This meant that if he found
a solution to

x 2 py 2 (mod n ) ,

≡

he could not predict a solution,

w 2 pz 2 (mod n ) ,

≡

distinct from the former. If he had been able to do this, he would have been
able to combine them as

( xw ) 2 ( pzy ) 2 (mod n )

≡

and have a factor of n provided that

xw ≡± pzy (mod n )

since we are back to congruence (C.2).
Gauss invented a method that differed from Legendre's scheme only in the
approach to finding small quadratic residues of n ; but his approach makes it
much more complicated (see [102, Articles 333 and 334, pages 403-406]).

In the 1920s, one individual expanded the idea, described above, of attempt-
ing to match the primes to create a square. We now look at his important

influence.

Kraitchik's Factoring Method Maurice Kraitchik determined that it
would suGce to find a multiple of n as a difference of squares in attempting
to factor it. For this purpose, he chose a polynomial of the form,

kn = ax 2 by 2 , ±

for some integer k , which allowed him to gain control over finding two distinct
residues at a given prime to form a square, which Legendre could not do. In other
words, Kraitchik used quadratic polynomials to get the residues, then multiplied
them to get squares (not a square times a small number). Kraitchik developed
this method over a period of more than 3 decades, a method later exploited by
D.H. Lehmer and R.E. Powers (see [145]). They employed Kraitchik's technique
but obtained their residues as Legendre had done. Later this was exploited in
the development of an algorithm that systematically extracted the best of the
above ideas as follows, which is taken from [169]. First we need to define a

couple of terms.
If B

is said to be a B - smooth number if all primes
dividing n are no larger than B , and B is called a smoothness bound .A factor
base is a set of “small” primes that remain the primes under consideration for
the algorithm at hand.

∈ N , then a number n ∈ N