Algoritmo p − 1 de Pollard

El algoritmo p - 1 de Pollard es un algoritmo de factorización de enteros en teoría de números, inventado por John Pollard en 1974. Es un algoritmo de propósito especial, lo que significa que es únicamente adecuado para enteros con factores de tipos específicos; es el ejemplo más simple de un algoritmo de factorización de grupos algebraico.

Los factores que encuentra son aquellos para los que el número que precede el factor, p - 1, es potencia lisa; la observación esencial es que, trabajando en el grupo multiplicativo módulo un número compuesto N, también se trabaja en los grupos multiplicativos módulo todos los factores de N'. La existencia de este algoritmo permite también el concepto de primos fuertes, siendo primos para los cuales p - 1 tiene al menos un factor primo grande. Casi todos los números primos lo suficientemente grandes son fuertes; si un primo usado para propósitos criptográficos resultara ser no fuerte, es mucho más probable que fuera por malicia que a través de un error de generación de números aleatorios.