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.