Milmore's Factoring Method An expansion of Fermat's conjecture that any composite is the difference between two squares yields a factoring methodology that is obviously more computer efficient than the "Sieve of Eratosthenes". Symbolically denoted as (T ^ 2) - (J ^ 2) = N, Where N is any number under consideration. The factors found are; the lower factor X = T - J and a higher factor Y = T + J. The exception, of course, are composites that are redundantly called "Perfect Squares". However, there are ways of rapidly detecting and solving this condition. The method involves using modulus 120 to both eliminate the trivial factors 2, 3 and 5 and to further classify the number under consideration. The thirty two remainders that are valid along with their required constants are listed below. Opposite the 32 remainders are listed the first number which is the lowest possible difference between two of the factors of the composite so identified by the remainder modulo 120. Note that a difference of two, the product of "Twin Primes", occurs in residue classes 23, 59, 83 and 119 when the multiplier of 120 is odd, denoted by the minus sign. Other interesting symmetries and similarities occur: remainders 7 and 67 are mirror images of each other as are 47 and 107. Half of the 32 valid remainders have two sets of constants, each determined by the multiplier of 120, either odd or even, denoted by the plus sign = even or the minus sign = odd. Each remainder value has from 2 to 12 cyclic additives that when repeatedly added to the initial estimated difference will eventually yield the difference between two factors of the composite as well as its factors. Any generated number when divided by two becomes the possible square root of the lower Square (J ^ 2) or J. With the addition of N to this square the resulting number becomes a possible (T ^ 2). If it is a valid square then the number is factored. After division of N by 120 is performed and the remainder and odd/even status of the quotient is observed the following generic algorithm is executed. 1. The first approximation or subsequent results of using the cyclic additive is divided by two. 2. The result is squared. 3. N, the number under consideration, is added. 4. The result is tested for being a "Perfect Square" by elimination of non-square attributes, then extracting the square root. 5. If not a square then add a cyclic additive and back to step 1. If a square then factors are (T+J) and (T-J). The methodology has been validated for all composites, squares excepted, up to 10 to the ninth power and is currently being evaluated for larger magnitudes with programs beyond BASIC, "C" or JAVA limitations. The process of square evaluation can be augmented with certain tests as well as other methods. It is obvious that square cannot have a unit?s digit of 2, 3, 7 or 8. It must also equal modulo 9 to either 0, 1 4 or 7. Other moduli such as 120 and 112 also limit what is a square, the latter being very effective. Additionally, for a large given N, such as a "RSA Challenge Number" of hundreds of digits, steps 1 through 3 may be combined to a few computer instructions to speed up the process. Note that if N is a square it is modulo 120 either equal to 1 or 49 among the other criteria. Obtaining the square root of any large number is not a prohibitive computer process. If a limit is added to the algorithm, that is the difference between number 7 and the integer equal to N divided by 7, then primality can be established if needed. Example of Milmore's Factorization Number 2,653 a composite of 7 times 379. Modulo 120 = 13. Mod 13 has only 1 set of constants so the 120 multiplier is ignored. Mod 13 first possible difference is 12 and the cyclic additive is 96 and 24. Iteration Additive Possible divided Squared Possible Square Number Difference by 2 Square status N added _________ ________ __________ _______ _______ ________ ______ 1 None 12 6 36 2,689 not 2 96 108 54 2,916 5,569 not 3 24 132 66 4,356 7,009 not 4 96 228 114 12,996 16,649 not 5 24 252 126 15,876 18,529 not 6 96 348 174 30,276 32,929 not 7 24 372 186 34,596 37,249 Bingo 37,249 is 193 squared. Hence, 193 minus 186 equals 7 and 193 plus 186 equals 379, the factors of 2,653. ______________________________________________________________ All of this will be covered in a forthcoming, soon to be published, book "On the Trail of the Lonesome Prime - A Methodology for Ascertaining Primality and Factorization". The book contains much more sophisticated and efficient techniques of factorization as well as non-probilistic prime number identification. johnmilmore@aol.com ? johnmilmore@hotmail.com March 7, 2010 Table of Constants used in Milmore's method of factorization. <--Mod 120 Residue Class <--Mod 120 multiplier, plus + = even, - minus = odd <---First Approximation to Difference between Factors <----------- Cyclic Additive --------------> ___________________________________________________________________ 1 24 72 24 24 7 + 6 48 132 48 12 7 - 66 48 12 48 132 11 + 10 16 44 4 12 20 28 20 12 4 44 16 20 11 - 14 20 12 4 44 16 20 16 44 4 12 20 28 13 12 96 24 17 16 40 8 40 32 19 + 18 12 48 84 48 12 36 19 - 42 48 12 36 12 48 84 23 + 22 16 20 60 4 60 20 16 44 23 - 2 60 20 16 44 16 20 60 4 29 20 8 24 16 24 8 40 __________________________________________________________ 31 + 30 36 48 12 48 36 60 31 - 6 48 36 60 36 48 12 37 36 48 72 41 16 24 16 8 16 24 32 43 + 42 60 36 60 84 43 - 18 60 84 60 36 47 + 14 20 12 48 52 48 12 20 28 47 - 26 48 12 20 28 20 12 48 52 49 48 24 48 48 53 28 24 16 24 56 59 + 10 12 16 20 12 48 4 48 12 20 16 12 20 59 - 2 48 12 20 16 12 20 12 16 20 12 48 4 ___________________________________________________________ 61 36 24 24 72 67 + 66 48 12 48 132 67 - 6 48 132 48 12 71 + 10 16 44 4 12 20 28 20 12 4 44 16 20 71 - 14 20 12 4 44 16 20 16 44 4 12 20 28 73 48 24 96 77 4 40 32 40 8 79 + 18 12 48 84 48 12 36 79 - 42 48 12 36 12 48 84 83 + 2 60 20 16 44 16 20 60 4 83 - 22 16 20 60 4 60 20 16 44 89 8 24 8 40 8 24 16 ___________________________________________________________ 91 + 6 48 36 60 36 48 12 91 - 30 36 48 12 48 36 60 97 24 72 48 101 4 16 24 32 24 16 8 103 + 42 60 36 60 84 103 - 18 60 84 60 36 107 + 26 48 12 20 28 20 12 48 52 107 - 14 20 12 48 52 48 12 20 28 109 12 48 48 24 113 8 24 56 24 16 119 + 10 12 16 20 12 48 4 48 12 20 16 12 20 119 - 2 48 12 20 16 12 20 12 16 20 12 48 4 ___________________________________________________________ johnmilmore@aol.com - johnmilmore@hotmail.com - March 7, 2010