While working with serial division/remainder method of finding factors, I have found that using knowns such as the known factors of a comparative number, or the difference between a number to be factored and its comparison number, then dividing into each number with the knowns and summing the remainders, the two original numbers will eventually be factored. This applies to many forms of cryptography, being dependent on products of large primes, which is hard to factor.
Following are three examples, each performed in a different way to get to the factors of the original number:
/First, find a number close to N=5048027 using an n-th triangular number; in this case I used N2=5051431 which is a product of 3179 x 1589, which is the sum of all numbers from 1 through 3178. I do this by taking sqrt of 5048027, multiplying by sqrt 2, then taking half rounded down for the two factors.
/Next, take the lower factor of 5051431, which is 1589, and divide it into both numbers (5048027 and 5051431), taking the remainder of each.
/ This results in 1363 and 0. Add them together, for a total of 1363.
/next, divide 1363 into both numbers (5048027 and 5051431), taking the remainders, which are 838 and 153. Add them together for a value of 991.
/divide 991 into both numbers again, and take remainders; 864+304=1168
/divide 1168 into both numbers, and sum remainders; 1099+999=2098 /divide 2098 into both numbers, and sum remainders; 1545+239=1784
/divide 1784 into both numbers, and sum remainders; 1091+927=2018
/divide 2018 into both numbers; the remainders are 1009 and 377.
1009 is one of the factors of the beginning number. I suppose that for each step you could divide the individual remainders into the original numbers to see if any divides evenly. Since dividing 2018 leaves a .5 value, it follows that 1009 divides into 2018 and 5048027. This was 7 steps total.
Example 2. For this example, I used 2x the difference between the starting N, N2. The numbers are 305713 and 783x391=306153. N2-N=306153-305713=440. 440x2=880, the starting divisor.
- /divide 880 into both numbers, for remainders of 353+793=1146
- /divide 1146, gives 171+877=1048
- /divide 1048, gives 745+137=882
- /882 gives 541+99=640
- /640 gives 433+233=666
- /666 gives 19+459=478
- /478 gives 271+711=982
- /982 gives 311+751. 311 is one of the factors of N (305713).
This is 8 steps total. Why did I choose 2x 440? As I remember it, I think I started with 440, and it took a lot longer. At some point, I realized that I had gotten to the point where 880 showed up, and was double of 440. It holds with the remainder addition, since the difference both ways of N and N2 is 440; at least that helps me make sense of it.
Example 3.
For this example, I used 21583 as the product to be factored, and this time I chose a comparative number that is 1 less than the next higher square; 149x151=22499. Since, in the matrix version where there are two columns of pairs of remainders in sequential rows, the answers are normally found in relation to the lower factor -1, that is where I started.
- /first, 21583 is divided by 148 (149-1). The remainder is 123. The sum method isn't used this time.
- /next, 22499 is divided by 123. The remainder is 113. 113 is a factor of 21583.
- /Now, take 21583 and divide by 150 (151-1). The remainder is 133.
- /divide 133 into 22499; the remainder is 22. When dividing 22499, the whole part of the answer is 169 (169.1654). Adding the whole part of 169 to the remainder equivalent of 22 equals 191. 191 is the other factor of 21583.
I don't know what to make of that. Thankfully there are real mathematicians who might be able to make sense of it.
I have included calculator screenshots showing my work. Most is condensed, with the previous remainders listed below the current operation. One of them has two factor pairs listed out of order, but I put it correctly in the written description.
Also, and VERY IMPORTANT, if you carry on from the point that I stopped in the examples, you will eventually get to all the factors of the numbers; the factor comparison numbers were not prime factor products, so eventually all of their factors are found. Eventually, the factor sum operations get to a loop; using the individual remainders from within the loop to carry on the operations will get to the remaining smaller factors.
Also, and I'm sure this is elementary math; subtracting two numbers with common factors, then subtracting the smaller numbers (a-b=c, b-c=d, and so forth), will eventually net the common factor. In the case of more than one common factor, it seems you end up with the product of them. Not sure what use that is, but it has helped me some in finding these factoring methods.
