Re: A Factoring Algorithm

In article <1132280903.901185.149820@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> "vernonner3voltazim" <vnemitz@xxxxxxxx> writes:
> (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. :)

It is indeed brute force, and not so very much faster. And something
similar has been done. Form your product G (as written). The common
way to proceed is to calculate the gcd of your H and G, which is faster
than your method. If it is not 1 you have found a divisor. The problem
with such methods is that you need to know all primes upto and including
the smallest prime divisor. With current factoring methods this is not
needed. And indeed, when you try to factor a (say) 160-digit number
you may need all the primes of upto 80 digits. That is something you
cannot even manage. On the other hand, factoring such numbers is done.
--
*** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~***/
.

Quantcast