--- In primenumbers@yahoogroups.com, Sudarshan Iyengar wrote:

>

> Hi,

>

> I have been wondering how exactly pari(http://pari.math.u-

> bordeaux.fr/) factors big integers(which are of 60 digit or more in

> length).

>

For PARI/GP, you can expose a lot of the internal factorization

process very easily. Turn on debug level 5, with the command

"\g 5" and then try to factor a big number:

? \g 5

debug = 5

? factorint(10^60+1)

... gives fairly detailed running commentary on how it

factors this number ...

Also, just ask for help on the factorint() command:

? ?factorint

factorint(x,{flag=0}): factor the integer x. flag is optional,

whose binary digits mean 1: avoid MPQS, 2: avoid first-stage ECM

(may fall back on it later), 4: avoid Pollard-Brent Rho and Shanks

SQUFOF, 8: skip final ECM (huge composites will be declared prime)

So this shows you right away that PARI uses any of MPQS, ECM,

Pollard-Brent Rho and Shanks SQUFOF algorithms to factor integers.

You can look at the PARI source code to learn more about these

algorithms, but realize that PARI is not primarily intended as

a factorization program, so the implementations within PARI may

be somewhat restricted in the size of the numbers, or may have

other compromises -- such as the fact that PARI will swap MPQS

information out to disk even if there is sufficient RAM available.