factorization algorithm in PARI/GP Which algorithm is used to factorize a number in PARI/GP?
It can factorize a number like $ 2^{257}-1 $ in few minutes. 
 A: According to this page from the PARI/GP website,

All arithmetic functions in the narrow sense of the word --- Euler's totient function, the Moebius function, the sums over divisors or powers of divisors etc.--- call, after trial division by small primes, the same versatile factoring machinery described under factorint. It includes Shanks SQUFOF, Pollard Rho, ECM and MPQS stages, and has an early exit option for the functions moebius ...

Later on in the same page: 

Factors the integer n into a product of pseudoprimes (see ispseudoprime), using a combination of the Shanks SQUFOF and Pollard Rho method (with modifications due to Brent), Lenstra's ECM (with modifications by Montgomery), and MPQS (the latter adapted from the LiDIA code with the kind permission of the LiDIA maintainers), as well as a search for pure powers. The output is a two-column matrix as for factor: the first column contains the "prime" divisors of n, the second one contains the (positive) exponents.

By the way, this is not that different from Mathematica, which also uses trial division to ferret out the small prime factors and more sophisticated algorithms for the larger prime factors.
