This Idea started while twiddling with variations on the Fermat Factoring Factoid (so, linked). The algebraic expressions 4x+1 and 4x+3 were talked-about.
Given that the variable C is used to represent an odd composite number that is not a perfect square, then the modulus of C to the Base of 4 will be either 1 or 3, and therefore either C=4x+1, or C=4x+3.
However, if C is an odd number, then the factors of C must also be odd numbers, so one factor might be represented as 4y+1 or 4y+3, and the other factor might be represented as 4z+1 or 4z+3. Since it is assumed we know C but don't know its factors, that means we don't know exactly which representations to use, of its factors.
But we can still play with algebra, so: C might equal (4y+1)(4z+1) = 16yz+4y+4z+1 C might equal (4y+3)(4z+1) = 16yz+4y+12z+3 Since y and z are both unknown values, it doesn't really matter if we had multiplied (4y+1)(4z+3) C might equal (4y+3)(4z+3) = 16yz+12y+12z+9 (note 9=8+1)
Those messy-looking results tell us something interesting. If we subtracted 1 from C and the result was divisible by 4, then we know that the factors of C must both be +1 or both be +3 of two multiples of 4. If we subtracted 3 from C and the result was divisible by 4, then one factor must be like 4y+3 and the other factor must be like 4z+1
As a **First Part** of explaining the Factoring Algorithm Idea here, let's try the number C=77. If we subtract 1 we see that the result is 76 and divisible by 4 (yields 19). That means we could modify the equation C=16yz+4y+4z+1 to become (C-1)/4 = 4yz+y+z = 19, OR modify the equation C=16yz+12y+12z+9 to become (C-1)/4 = 4yz+3y+3z+2 = 19 --we don't know which is correct if we don't know the factors of C.
But since 19 is smaller than 77, it might be worthwhile to try to find which values of y and z work. A little bit more algebra, and we can obtain a fairly simple way of making guesses. If 19=4yz+y+z, then 19=y(4z+1)+z, and therefore (19-z)/(4z+1)=y. That means we can try different values of z, and see what values for y pop out. (Also note that y and z must be different from each other, else C would be a perfect square, and we are not allowing that here.)
Before we actually do some trials, look at that (4z+1), and then look a few paragraphs higher to see this: {C might equal (4y+1)(4z+1)} Even though we will be working with 19 instead of 77, we sill will be trying possible direct factors of C.
So, here are some trials: z=0; 4z+1=1; y=(19-0)/1 = 19, not useful; everything is divisible by 1. z=1; 4z+1=5; y=(19-1)/5 = 18/5 = doesn't divide evenly z=2; 4z+1=9; y=(19-2)/9 = 17/9 = doesn't divide evenly AND we can stop because the result is 1-and-a-fraction; no future calculation on this list can produce any whole-number value for y greater than 1.
So that means the other original equation must have the answer we seek: C WILL equal (4y+3)(4z+3) = 16yz+12y+12z+9 Instead of subtracting 1 from 77, we can subtract 9, so: (C-9)/4 = 17 = 4yz+3y+3z = y(4z+3)+3z (17-3z)/(4z+3)=y, and so the trials begin: z=0; 3z=0; 4z+3=3; y=(17-0)/3 = 17/3 = doesn't divide evenly z=1; 3z=3; 4z+3=7; y=(17-3)/7 = 14/7 = 2
So z=1 and y=2 and that means since C=(4y+3)(4z+3), the factors of C are 4z+3=7 (see above about working our trials with an actual factor of C) and 4y+3=11. You probably knew the factors already, :).
But that's only the First Part of this Factoring Algorithm. If C was a quite-large number, 1/4 of it would still be a quite-large number, and it could take a quite-large number of trials to compute y from z. So the Second Part is to Exponentially Reduce the number of trials, by always assuming z=1.
Well, there's more to it than that, of course. We have to arrange our algebraic manipulations to produce situations in which z must equal 1. It CAN be done! We just can't use that number (4) so frequently played-with above.
For our Second Part of this Factoring Algorithm, we need a larger number than 77; I'll pick C=1234567. Since it is Standard Operating Procedure to test a number in certain ways, such as by ensuring it is not a perfect square, and doing some direct trial divisions, let's assume that has been done. For this explanation we will have limited our direct trial divisions of 1234567 to 3, 5, and 7, and found none of those is a factor.
When z=1, 4z+1=5 and 4z+3=7, and we've already tried those above, so that is why we won't be using (4) like we did before. We'll start with 8, which is twice 4. If necessary, as our trials proceed and possibly fail, we can double 8 to work with 16, and later double 16 to work with 32, and so on. ONE of the factors of 1234567 MUST exist as a number that can be described (when z=1) as 8z+j, or 16z+j, or 32z+j, OR so-on, until we find it. And since that doubling counts as an exponential series, perhaps it won't take long to find that factor, right?
Well, maybe. There's another exponential associated with that "j" I sneaked into those expressions in the previous paragraph, and that second exponential thing counts as "a fly in the ointment". You'll be seeing what I mean shortly.
So, start with 8z, where z=1, and think about numbers smaller than 8z=8. We already tried them, in those trial divisions mentioned above. That's why we know we can safely start with z=1. Therefore, what about the "j" in the more-complete equation (8z+j= a factor of C)?
There are only four possible values of j, when C is an odd number: 1, 3, 5, and 7. That's because if we used 9 we would have the expression 8z+9 which equals 8z+8+1 which equals 8(z+1)+1, and that means we would essentially be working with z=2 instead of z=1.
Now since C has two factors, and we are only working to ensure one of them equals 8z+j when z=1, we have no idea what the other factor will be, other than something like 8y+k. We are going to need a multiplication table, of possible values of j multiplied by possible values of k: 01 03 05 07 03 09 15 21 05 15 25 35 07 21 35 49 That is, if C equals 8z+j multiplied by 8y+k, the results are C=64yz+8jy+8kz+jk --the "jk" is a number in the table, and if we subtracted jk from C, the result must be divisible by 8.
Next, we need to remember something previously from earlier in this presentation, when we were working with (4): {C might equal (4y+1)(4z+1) = 16yz+4y+4z+1 C might equal (4y+3)(4z+3) = 16yz+12y+12z+9 (note 9=8+1)} In our example of 77, dividing it by 4 gave us a remainder of 1, and thus we knew we needed a complicated expression that was divisible by 4, after subtracting 1. In the case of our new example 1234567, dividing by 8 gives us a remainder of 7. That means our 8z+j and 8y+k must multiply to produce a complicated expression such that after we subtract 7, the result is divisible by 8. Therefore we need to modify that multiplication table to get the remainders, after dividing by 8: 01 03 05 07 03 01 07 05 05 07 01 03 07 05 03 01
The diagonal of "1"s does NOT actually represent perfect squares, since we are assuming z=1 and y could be wildly different from that. But half of the table, on one side of that diagonal or the other, can be ignored because it is basically duplicate data. Recall this: {{C might equal (4y+3)(4z+1) = 16yz+4y+12z+3} Since y and z are both unknown values, it doesn't really matter if we had multiplied (4y+1)(4z+3)}
Therefore, for the purposes of this explanation, we'll consider paying attention only to the upper-right portion of the table. So, since only two numbers in that portion of the table are relevant 7s, there are only two tests we need to think about doing, with respect to 8z+j, which are 8z+5 and 8z+7.
If z=1, then 8z+5=13. Now remember this from the First Part: {Before we actually do some trials, look at that (4z+1), and then look a few paragraphs higher to see this: C might equal (4y+1)(4z+1) Even though we will be working with 19 instead of 77, we sill will be trying possible direct factors of C.}
So why not just directly try dividing into our new example number, 1234567? Wouldn't that save some time? If so, well, 1234567 is not evenly divisible by 13. Note that if it HAD been divisible by 13, the other factor of C MUST have the form of 8y+3, thanks to that key remainder of 7 (when dividing 1234567 by 8). And that's why we don't need to divide 1234567 by 8z+3=11. I suspect this will lead to some discussion in the annos, but I'm pretty confident. If the remainder had been 1 instead of 7, we would have had to pay attention to all the 1s in the diagonal of that table....
As for 8z+7=15, 15 is divisible by 3 (and 5), and we already know 1234567 isn't divisible by 3 (or 5), so we don't need to try that division, after all.
The 2nd link has some more "remainderized" multiplication tables, relevant to using 16, 32, and 64. IT JUST HAPPENS that when any of those three numbers is divided into 1234567, the remainder is still 7. One should not normally expect any such thing, when using this Exponential Algorithm.
You will be able to see the other exponential thing, the fly in the ointment for this HalfBaked Idea. The number-of-7s/number- of-tests-to-do doubles, from each table to the next!
On the other hand, the 7s (or other numbers) form predictable patterns, making them easy to compute, without computing the entire modified multiplication table.-- Vernon, Apr 23 2016 Fermat Factoring Factoid Fermat_20Factoring_20FactoidAs mentioned in the main text. [Vernon, Apr 23 2016] Modified Multiplication Tables http://www.nemitz.n...rnon/mod64mults.pngAs mentioned in the main text. [Vernon, Apr 23 2016] This is an utterly sane proposal, and I vote for immediate implementation, albeit without the headphones.-- Toto Anders, Apr 23 2016 You're gonna need a bigger margin.-- MaxwellBuchanan, Apr 23 2016 Did anybody make a Cliff's Notes version?-- RayfordSteele, Apr 23 2016 Ow. Cool, but ow.
Can you flit with numbers like that without paper or anything Vernon?I kind of get it. Makes my head hurt.-- 2 fries shy of a happy meal, Apr 24 2016 wait... no I don't get it.
ow-- 2 fries shy of a happy meal, Apr 24 2016 [2fries], I tried to explain the Idea clearly, but understanding basic algebra is essential. One thing about multiplying algebraic terms might be helpful, if you didn't know it already, can be demonstrated this way: 4y+1 multiplied by 4z+1 works just like ordinary 2-digit multiplication like 41 (or 40+1) times 41 (or 40+1) ---you get this: 1+40+40+1600, each is a partial product, and then you add those partial products. But algebraic partial products can't always be added together, so: 1+4y+4z+16yz --all you can do here is try to organize the partial products neatly: 16yz+4y+4z+1 (it is standard to put the most- complicated term first, and the simplest term last)
Also, any time you see something like this: {8z+9 which equals 8z+8+1 which equals 8(z+1)+1}, part of that last thing, 8(z+1), refers to multiplying 8 times z+1, equivalent to the 8z+8 in the middle part of the enbraced text.
In reviewing the main text, I noticed that a bit more explanation was needed in the vicinity of the first multiplication table. Perhaps that will help.-- Vernon, Apr 24 2016 I think I understand it except for the "fly in the ointment" part. I read through the rest but didn't see what that was supposed to be. Maybe I just wasn't paying sufficient attention.
The other part I didn't understand is how this is slow (i.e. not a danger to encryption).-- notexactly, Apr 24 2016 Holy shit. Just holy shit.-- blissmiss, Apr 24 2016 [notexactly], the number of tests (to find a factor) goes down by using exponentially larger base-values (8, 16, 32, 64, ...) but goes up as the number of tests to try per base- value exponentially goes up (in the example, the number of 7s keeps doubling). It basically balances out, leaving us with performing too many tests to be practical, for encryption-level composite numbers.-- Vernon, Apr 24 2016 Is this the "New Math"?-- whatrock, Apr 24 2016 I guess when I commented earlier I didn't understand that the two parts that I didn't understand were the same part.-- notexactly, Apr 25 2016 Maybe this would be better as a Youtube or chalkboard demo.-- RayfordSteele, Apr 25 2016 random, halfbakery