A Factoring Algorithm

A Factoring Algorithm

Not so long ago I posted another message by this title in this Thread.
This is a different algorithm than that one. Is it any better? Maybe.
Is it already well known? Maybe! But at least I had fun thinking it
up, and perhaps you might find it interesting, if you don't happen to
know about it.

This algorithm begins by thinking about numbers divisible by 5.
Why is it so easy to spot a number divisible by 5? Because we
write our numbers in Base Ten, a quantity perfectly divisible by 5.
This observation IS extendable to other numbers and other Bases!
(Yes, I know I am about to suggest something of a brute-force
approach to factoring, but I'm certain it is a FASTER brute-force
approach than the normal method of dividing a huge number by
all the primes-smaller-than-its-square-root. At least a little bit
faster. :)

Start with some huge number H you want to try to factor.
Now start with the List of Primes (you can ignore 2 if the huge
number is odd, of course). Create the product of multiplying
the sequence of primes 3 * 5 * 7 * 11 * 13 * ... * P, until you have
created a new huge number G that is SMALLER than H. If you
include one more prime past P into G, the product would be
bigger than H.

Let us now think about "writing" H in terms of Base G. Because
of the way G was defined, we will be dealing with at most a two-
digit number. Like in Base Ten, there will be a "ones" column
in which to place some symbol representing one of the values
0, 1, 2, 3, ..., (G-1). Then there will be a "G's" column, just like
the ordinary second "Tens" column in Base Ten. Because of the
way G was defined, we can divide G into H to obtain the numerical
value of the "digit" (I'll call it N) that goes into this column.
Next, we take the product N*G and subtract this from H to obtain
the numerical value (I'll call it V) of the "digit" that goes into the
"ones" column.

Now for the sneaky trick: IF H is divisible by ANY of the primes
that went into constructing G, then V is ALSO divisible by that
prime, for exactly the same reason that numbers divisible by 5,
in Base Ten, are obviously divisible by 5. We may now do
brute-force divisions upon the vastly smaller number V (it's NOT
obviously divisible, alas), much more quickly than by dividing
into H.

If none of the primes up to P divide into V, then we simply start
constructing a NEW Base G, from the primes that follow P:
Q * R * S * ... * T. As before, we use this new Base G to find
new values N and V. As before, if H is divisible by any of the
primes that went into constructing G, then V is also divisible by
one of those primes. We repeat the algorithm until either H is
factored, or shown to be prime.

.