 Introduction
There are very few brain breaking total horror show problems in math that are
more difficult than factoring an integer. This sounds almost as if it is some
sort of a joke. Really? Just take a number, any number, make it a positive
integer and then find the prime factors for the thing. How tough can that be?
 Keep it simple and stupid
For giggles we can look at some easy number such as 123. This is not really
such a difficult problem to figure out what can divide into that neatly. Here
I say "neatly" because I do not want to see a fraction no one can reduce nor
a big long string of digits after the decimal place. Try 7/3 for fun. You just
can not do much with that other than say there are two chunks of 3 in the seven.
Also you end up with something left over. So you get 2 as a result with a 1/3
fraction hanging around. You are stuck with it. Try to write 1/3 as a decimal
number and you will need a lot of paper. It is a repeating digit of "3" after
the decimal place. Forever. Endlessly. In this example of 7/3 we have no way to
ever get a perfect integer result. Why? Likely this is because both numbers
involved are prime numbers. Sounds easy right? Well let us take a look at the
number 123. What can we divide into that neatly? Another question is how do we
pick the "test" numbers? Let us be stupid and just start at the number 1 and go
upwards from there. Trivial. Golly gee whiz but we can divide 123 by 1 with no
left over fractions. Gee. No surprise. Can we agree that 1 will divide into any
number you choose other than zero. Do not get fancy with me! What about the next
integer which is 2? Nope. We can see that 123 is an odd number because we can
not divide it evenly ( or neatly ) by 2. Try the number 3 and then 4 and then
onwards up the list all the way to 123. No big surprise that we can divide 123
by itself. Gee that is dumb. So 123 can divide by 123 to give the result 1. Also
we can divide 123 by the value 1. If anyone bothers to check every value upward
from 1 through to 123 then you get only two possible perfect results at 3 and
also at 41. Nothing else can divide into 123 neatly. Therefore we can say that
the factors of 123 are the numbers 1 and 3 and 41 and also 123. Nothing else can
go neatly.
Is there a better way than testing every integer upwards from 1 to the value in
question?
 Not entirely stupid
If we continue to play around with the number 123 then we have to start asking
some questions. Firstly there is the result we get when we divide 123 by a valid
perfect "neat" factor of 3. Here we get the result 41. In fact we can say that
testing every integer upwards from 1 will give some result that hits a high
level maximum. Even if the result is not "neat" we will see that values past 11
simply get smaller again. Let us take a look at some results of test values :
test divisor test number result of division

1 123 123 exactly
2 123 61.5
3 123 41 exactly
4 123 30.75
5 123 24.6
6 123 20.5
7 123 17.571428571428.... endless
8 123 15.375
9 123 13.666666666666.... endless
10 123 12.3
11 123 11.181818181818.... endless
12 123 10.25
13 123 9.461538461538..... even more ...
14 123 8.785714285714... yeah .. endless
15 123 8.2
16 123 7.6875
.
.
.
39 123 3.153846153846.... you figure it out
40 123 3.075
41 123 3 exactly
42 123 2.928571428571.... etc etc etc
.
.
.
121 123 1.016528925619834710743801652892561983471074380165289256198347107438016528925619834710743801652892561983471074380165289256... forever ... endless repeating 01652892561983471074380 .....
122 123 1.00819672131147540983606557377049180327868852459016393442622950819672131147540983606557377049180327868852459016393442622950..... forever repeating the 819672... sequence
123 123 1 precisely

The above table is a blunt force dumb test of every integer from 1 upwards to
the value 123. This works! There we can see that some numbers will give a nice
"neat" flawless result in the division. However there is a funny thing that
happens after we try 11. The result of the division gets smaller. Every thing
we look at afterwards seems to result in a smaller number. Why? For this we need
a bit of trivial easy dirt simple geometry :
^


 2 This is a perfect square
+*
crazy things are over  
here and we call them   2
negative numbers  
 
<xxxxx+1+345>
5 4 3  
 
  The area of both of these perfect
This thing is   square regions is 2 x 2 = 4
also a perfect ++
square 2 

V
Look at the idea of 2 on a number line. This is 1 unit past the 1 unit past zero
and that can keep you busy for a while if you think on it. Entire civilizations
have been born into existance and vanished with no concept of zero as a number.
How many sheep does it take to manage a field of grass where there is no grass
and you are in a desert in the dark? Can we just agree that five goats minus
five goats will leave you with no goats. How do you write that down? OKay do you
know how to write your ideas on clay or paper or stone? Geez this can get ugly
if you ponder it. Can we agree that zero exists? Is there a way to say that you
may have an integer value of zero and that is a valid number? We can save about
nine hundred years of human civilization in this agreement. Even worse, and here
we need to be careful, what happens when we divide a number by zero?
We see in the above graph that a region with area 4 may be described as a simple
square with sides of length 2. We can measure this length of 2 on a number line
and just move away from the zero origin in the centre. In truth we can go in any
direction we want and then make a right angle and go another 2 units. For the
sake of simplicity I draw two squares where one of them is in the upper right
quadrant of positive numbers. The other square is drawn in the lower left with
the negative numbers. In this way it is easy to explain that (2) x (2) does in
fact result in a positive value of 4. The geometry will still work anywhere we
choose to draw the square but we really want both sides to have the same length
and for the sake of simplicity we also want both numbers to be equal on any side
of any number line we choose. This makes the idea of a square root really clear.
Can we make a region with straight lines and also an area of 4 where the sides
are not equal? In fact there are an infinite number of possible solutions that
all have area of 4. If we are restricted to just integer values then there are
very few solutions indeed. We can have 1 x 4 = 4 and then 2 x 2 = 4. There also
exists the negative numbers (1) x (4) but that does not tell us very much
about the possible integer factors of four. In fact, it may be a waste of time
to ponder the negative numbers at this time. Otherwise we may fall into the trap
of asking for the square root of a negative number. Perfectly valid to ask about
such things but not helpful at this time. The key observation here is that one
may only create a simple polygon of four sides with integer length sides and
perfect right angles by using either a square root value or a length shorter
than the square root. There is no promise that an integer square root exists at
all. Regardless of this limitation there is no valid reason to ask for all the
possible division tests of a number like 123 other than values up to and also
including the square root. All possible integer results will exist by pondering
trivial geometry of a trivial polygon.
 Sometimes the answer is "no"
Can we make a trivial polygon of four sides with an enclosed area of 7 or 17 and
what about the value 127? We can make an infinite number of such polygons but
again we are restricted to integer values only. Then the problem becomes nasty.
Let us once again do the division trial tests. This time we test the number 127
with every possible integer up to the square root :
test divisor test number result of division

1 127 127 exactly
2 127 63.5
3 127 42.333333333333333....
4 127 31.75
5 127 25.4
6 127 21.166666666666666....
7 127 18.142857142857142857...
8 127 15.875
9 127 14.111111111111111....
10 127 12.7
11 127 11.54545454545454.....
square root limit is 11.269427669584644882850003.....

Looking at the results we see there is no such thing as a "neat" integer result
to be found. For this result set we now know that the only way to divide 127 by
an integer and get an integer result is the value 1 and of course 127. Nothing
else works. Therefore the value 127 is called a "prime" number. A more strict
definition of a prime number is any positive value which has two perfect integer
factors of itself and 1. Therefore the value 1 is not prime. Having done the
trial division test above we also know that 127 is a prime number. Why does this
matter when factoring any number?
 Prime factors only please
We can choose any integer at all and begin to find the factors that are "neat"
perfect integer results of a trial division. However we do not really need to
trial test all the integers up to the square root. Consider a much larger value
such as 39,916,800. Here we see that we are not playing around with trivial
stuff because the square root of that is about 6317.97. Were we to perform the
trial division tests of all integers up to 6317 then the results table would be
very long indeed. There has to be a better way. This is where prime factors
begin to play heavily on the problem. Firstly we know that a prime number can
not be factored by anything other than itself and 1. Once we find a prime that
can divide into some test value we know there may be multiples of that given
prime factor but never anything else that can divide into the prime factor. That
s not at all trivial to see unless we test 39,916,800 for prime factors and see
the actual results. Sometimes an experiment is worth its weight in latinum:
test divisor test number result of division

1 39916800 39916800 exactly
2 39916800 19958400 exactly

Just stop right there. We know that 2 is a prime number. It can only be factored
by itself and 1 and thus 2 is a prime number. In this first trial we have found
a prime factor of 2. We also know there is no smaller prime factor either. Well
gee, the number 2 is the first prime so that is easy. The real question here is
how many times can we divide 2 into the result and always get a perfect "neat"
integer?
test divisor test number result of division

1 39916800 39916800 exactly
2 39916800 19958400 exactly
2 19958400 9979200 also perfect
2 9979200 4989600 keep on going
2 4989600 2494800 yes
2 2494800 1247400 this gets better
2 1247400 623700 and keeps going
2 623700 311850 when will it end?
2 311850 155925 right about here right?
2 155925 77962.5 not a perfect integer

know when to stop playing with the prime factor 2
If we look at the results above we see that the prime factor 2 will divide into
each remainder quite "neat" for a total of eight times. This means we may forget
about ever trying another variation of the number 2 ever again. Why test with
the number 4 when we already know that 4 = 2 x 2 and clearly the prime factor 2
has fully reduced the test number down to 155925. Every possible power of 2 has
been divided out of the test case. In fact we can forget about 8 as a test case
and that includes 16 and upwards to other powers of 2. They are all tested and
no longer of concern once we eliminate every division test with prime factor 2.
In fact, once we are done with the number 2 then we can say that all possible
even numbers are done forever. That really cuts the trial division process down
to half of our list upwards to 6317.
Let us now move upwards to the number 3. If we ponder a bit here we can see that
this is another prime number. There is no way to divide 3 by 2 and get a perfect
integer result. We certainly do not need to test anything else. Divide by 1 is
a given of course but what else is there? So here we have another prime factor
test case and we begin with the last valid result from above :
test divisor test number result of division

3 155925 51975 perfect
3 51975 17325
3 17325 5775
3 5775 1925 we keep going until what?
3 1925 641.6666666666666666....

We just tested with the prime factor 3 until there was no longer a perfect neat
integer result. A total of four tests result in success. With this test phase we
have now taken care of every possible power of 3 forever. The list of test cases
is falling fast. With the prime factor 2 we were able to cut the list in half.
With the elimination of all possible powers of 3 we have knocked that test case
list down again. What is next? There is no need to ponder 4 at all. We removed
all possible powers of 2 and that means all even numbers. Actually a little time
thinking will show that we also removed all possible variations of 2 x 3 which
means helf of the powers of 3 were gone long ago. Move along upwards to the next
number which is 5. Here again we see that we can not divide 5 in any "neat" way
with 2 or 3. There are no other smaller prime factors to test. Therefore we will
begin with the last valid result from above :
test divisor test number result of division

5 1925 385
5 385 77
5 77 15.4

At this point we have reduced the test case number down to 77. At a glance we
can guess that a two digit number with the same digits has a factor called 11.
Is there anything smaller? What else could we test? How about 7 as a trivial
test case. In fact we already know that 7 x 11 = 77. There is no reason to go
further as there are no other factors. In fact, there are no other prime factors
to ponder here. Both 7 and 11 are prime numbers and this ends the factorization
of the large number 39,916,800. As a summary we will now say that the prime
factors of 39,916,800 are
2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 3 x 3 x 3 x 3 x 5 x 5 x 7 x 11
or more simply
2^8 x 3^4 x 5^2 x 7 x 11 = 39916800
 Prime numbers matter. How do we find them?
From the above experiments we can see that we can reduce a larger number down to
its prime factors. Well maybe we can. There is no promise here. What if we were
to try and factor the number 12377 or perhaps 12379? Feel free to test those out
and you will find that they are both prime numbers. There are no factors at all
other than 1 and the test number. Feel free to try 12373 also. That is a prime
number also. There are a lot of prime numbers. In fact, there is an infinite
supply of them. Sometimes we can find two prime numbers of the form p and p+2
where we call them a "prime pair". The numbers 12377 and 12379 are an example of
a prime pair. Consider what happens when you multiply them :
12377 x 12379 = 153214883
The resultant number 153,214,883 is what we call a "composite" number. In this
case we can say the five digit prime numbers 12377 and 12379 will multiply to
give us a composite nine digit result. This may be expressed as p5 x p5 = c9
where we know we have two prime numbers of five digits and therefore the result
must be a composite. The fact that the composite result is nine digits is not at
all the case with all five digit prime factors. The p5 primes 31607 and 31643
will multiply to give up a c10 = 1000140301. Here we may list a few examples of
c10 composites that have only two p5 factors :
c10 = p5 x p5

1000000081 = 26881 x 37201
1000006087 = 31357 x 31891
1000022411 = 27773 x 36007
1000140301 = 31607 x 31643
1000267129 = 31627 x 31627
1000329943 = 31607 x 31649
1000773161 = 31627 x 31643
.
.
.
This is a very long list
.
.
.
9996200261 = 99991 x 99971
9997800121 = 99989 x 99989
9998000099 = 99991 x 99989
9998200081 = 99991 x 99991

Those are all ten digit composite numbers with only two factors and both prime
factors are five digits each. This is not a common situation and in general we
see composite numbers with many factors of various sizes. The largest ten digit
composite with many very small factors is :
3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 7 x 11 x 13 x 13 x 13 = 9989260281
One may argue that surely an even number would also include the number 2 as a
factor but that would be trivial to see at a glance. However composite numbers
which are comprised of powers of two may be of great interest to us.

t h i s i s a w o r k i n p r o g r e s s

geez .. how am I going to introduce modulo and congruence ? sort of
necessary ideas for factoring algorithms ... damn it.
SIGSEGNO < this means no and no means no
A worthy pioner! once more remove, good friend.
Horatio: O day and night, but this is wondrous strange!
Hamlet: And therefore as a stranger give it welcome.
There are more things in heaven and earth, Horatio,
Than are dreamt of in your philosophy.
[ Hamlet, Prince of Denmark, William Shakespeare ]
note ... describe essential sieve, then some lucas lehmer and then
Sophie Germain and then we move on to field theory with GNFS but
finally land on Pollard Rho for fun. nuff said ... for now ..