- 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 | | | | <-------x----x----x----x----x----+----1----+----3----4----5--------> -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 ..