We will use the following notation throughout this book. The **integers** are

Since divides all integers, we sometimes call a ``trival factor'' and the factors greater than the ``non-trivial factors''.

**proof**: implies that and implies that . Therefore:

A problem on cryptography which we will encounter later in this chapter involves factoring large numbers. In particular, consider the following question: What is the fastest general procedure to find the smallest non-trivial positive factor of an integer ? This question may seem simple but if is very large the answer is far from obvious. For example, consider the following 309-digit number

13506641086599522334960321627880596993888147560566702752448514385152 65106048595338339402871505719094417982072821644715513736804197039641 91743046496589274256239341020864383202110372958725762358509643110564 07350150818751067659462920556368552947521350085287941637732853390610 9750544334999811150056977236890927563This number is called RSA-1024, since it has 1024 binary digits. The sum of its digits is 1369. If you can factor this number then RSA Security Inc will give you one hundred thousand dollars! See

http://www.rsasecurity.com/rsalabs/challenges/factoring/index.htmlfor more details.

However, if is relatively small then there are some easy strategies to follow to factor it.

**proof**: Suppose that this statement were false, so and . Then . This is a contradiction, so either or .

The result above implies that,

- if is composite then the smallest non-trivial factor of must satisfy ,
- if has no factor where then must be a prime.

*What about the factors of ? By the above fact, to find a positive factor of , we need only check if the integers divide since . Again, it must be odd and our first try, turns out to be an integer and we get .*

*To factor we check if divide since . Trying all the odd numbers , we see that none of them are divisors of .*

*The complete factorization is .*

The following notation is quite useful, as we will see in the next section.

The set of all multiples of is denoted

This may be visualized as the first column of the array which you get by listing all the integers in strings of -at-a-time,or as a real number line with a ``notch'' every units. which we may also visualize as the first column of the array

David Joyner 2007-09-03