algoritmo de factorización en PARI/GP

Question

¿Qué algoritmo se utiliza para factorizar un número en PARI/GP? Puede factorizar un número como $ 2^{257}-1 $ en pocos minutos.

Answer 1

Según esta página del sitio web de PARI/GP ,

Todas las funciones aritméticas en el sentido estricto de la palabra ---la función totiente de Euler, la función de Moebius, las sumas sobre divisores o potencias de divisores, etc.--- llaman, después de la división de prueba por primos pequeños, a la misma maquinaria versátil de factorización descrita en factorint . Incluye las etapas Shanks SQUFOF, Pollard Rho, ECM y MPQS, y tiene una opción de salida anticipada para las funciones moebius ...

Más adelante en la misma página:

Factoriza el número entero n en un producto de pseudoprimos (véase ispseudoprime), utilizando una combinación del método SQUFOF de Shanks y Rho de Pollard (con modificaciones debidas a Brent), el ECM de Lenstra (con modificaciones de Montgomery), y MPQS (este último adaptado del código de LiDIA con el amable permiso de los mantenedores de LiDIA), así como una búsqueda de potencias puras. La salida es una matriz de dos columnas como para factor La primera columna contiene los divisores "primos" de n, la segunda contiene los exponentes (positivos).

Por cierto, esto no es tan diferente de Mathematica, que también utiliza la división de prueba para descubrir los factores primos pequeños y algoritmos más sofisticados para los factores primos más grandes.