Here is a factoring algorithm that seems to me might not
take as many computation steps as most. Nevertheless,
it
is still impractical, as shall shortly be seen.
Consider some composite number (c) that we wish to
factor --find two numbers (a) and (b) such that when
multiplied together,
their product is (c). It is widely
known that if one computes the square root of (c), one
of
its factors will be smaller than that square-root, and one
will be larger (provided (c) was not a perfect square, of
course!).
Next, I happen to have a scientific calculator that has a
"factorial" button. I can specify a number like 50, and it
will compute 1 times 2 times 3 times 4 times 5 times 6
...
up to and including 50. The result is approximate, and I
THINK the calculator does not actually do all those
individual multiplications --some sort of shortcut like
adding logarithms is probably involved.
Here I will assume that the "shortcut", whatever it is, is
efficient enough to compute a quite-large factorial in a
reasonable time. This is where the impracticality of this
Idea begins to become apparent. We need a highly
accurate answer, not just an approximation!
What we need it for (I'll get back to the impracticality in
a
bit) is the last part of the algorithm, which invokes the
Greatest Common Divisor function. Let me provide an
example, using (c)=209.
The square root of 209 is 14.irrational, so that means one
of the factors of 209 is 14 or less (well, not 14 because
that is
an
even number, and 209 is odd). Let's therefore compute
the factorial of 13, which is 6227020800. When we plug
that number and 209 into the Greatest Common Divisor
function ... it works (pretty efficiently!) like this:
Divide 6227020800 by 209 to get 29794357 and a
remainder
of 187. Now divide 209 by 187 to get 1 and remainder
of
22. Now divide 187 by 22 to get 8 and a remainder of
11. (Every just-found remainder becomes the divisor
into the previous divisor.)
Now divide 22 by 11 to get 2, exactly. Therefore 11
must
be a common divisor --a factor!-- of both 209 and our
initial factorial. (When no new remainder is found, the
common divisor is always the last-found remainder, the
last divisor.
Note the function ALWAYS finds a
common divisor, even if it is simply the number 1.)
The impracticality is, when (c) is a large number, the
factorial we need will be a number so vast it literally
cannot be processed, having more digits than the total
number of atoms in the Universe. Being able to compute
the needed factorial in relatively few STEPS is not useful
if
the last step requires a computer that just plain can
never
be built!
Ah well. For the HalfBakery, though, this Idea could still
be worthy of posting. I hope you enjoyed it.