Algorithm for extracting the prime factors of an integer

[Paul Rubin]

"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.