Algorithm for extracting the prime factors of an integer

[Dario Alpern]

Paul Rubin <phr-n2002b at NOSPAMnightsong.com> wrote in message news:<7xwultbeym.fsf at ruckus.brouhaha.com>...
> "Luca Bruderer" <luca.bruderer at bluewin.ch> writes:
> > I'm wondering which is the best algorithm to do this.
> 
> Factoring integers of larger than 20 digits or so is a very
> complicated subject.  A good introduction can be found in "A Course in
> Number Theory and Cryptography" by Neal Koblitz.
> 
> For less than 20 digits you can use dumb brute force algorithms and
> still get answers in a tolerable amount of time.
> 
> The largest publicly known factorizations of "hard" composites (i.e.
> numbers with no small factors and no special properties that make them
> easier to factor) are in the range of 155 digits.  Factoring those
> numbers took thousands of CPU-years (i.e. several thousand computers
> crunching in parallel for months nonstop).
> 
> The MIRACL package (http://indigo.ie/~mscott) contains a factoring
> program that can factor numbers up to 80 digits or so on a single PC.

... or you can use the Java applet located at:

http://www.alpertron.com.ar/ECM.HTM

that also factors any number up to 80 digits or find prime factors of
up to about 30 digits of numbers up to 1000 digits long. The source
code is included, and you can adapt it for any non-commercial use (see
source code header).

Best regards,

Dario Alejandro Alpern
Buenos Aires - Argentina
http://www.alpertron.com.ar/ENGLISH.HTM