Factorial Factoring

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.