The Integers - Introduction to Cryptography with Java Applets - page 67

PROPOSITION 6 If n is composite, then n has a prime factor not exceeding the square

root of n .

Proof. Suppose n is the product of integers b and c , and say 1 < b ≤ c < n . Note that b is

no greater than √ n

ause if it were, c would also be greater than n , implying that bc > n

b c

· n = n , a contradiction. Proposition 4 says that b must have a prime divisor, which must

also divide n by Proposition 1. Thus, a prime divisor smaller than n exists.

The previous result tells us that if we wish to search sequentially for a prime factor of some
number , we need not exceed its square root. This can reduce our workload considerably. For

example, if we wish to know whether or not 101 is prime, we need only search for factors up
to 10, which is the largest integer

n

. We check for factors in Table 3.1.
We conclude, therefore, that 101 is prime. Proposition 6 proves it is not necessary to
search for factors of 101 greater than 10, for one such factor, if it exists, must be

≤ 101

10.
This sequential method for determining whether or not numbers are prime is known as
trial division by small primes.
Say we want to find a prime factor of an integer consisting of 500 decimal digits. (This
is typical in modern cryptography.) Then the square root of that number would still be about
250 decimal digits. Asking the computer to search each number in a sequential fashion up
to the square root would take an enormous amount of time. Thus, trial division is limited to
integers having small prime factors. If we want to factor large integers, we must find bet-
ter methods of factoring.
We can speed up trial division by noting that it isn't necessary to divide by every inte-
ger not exceeding the square root of

≤

n , but only those integers which are prime. If we make

Table 3.1

# Factor of 101?

2 No

3 No

4 No

5 No

6 No

7 No

8 No

9 No

10 No