Factorización de Pollard p−1

El método p menos uno de Pollard es un algoritmo clásico de factorización de enteros que halla un factor no trivial de un módulo compuesto n cuando al menos un factor primo p de n tiene la propiedad de que p menos uno es suave respecto de una cota B elegida: cada potencia prima en la factorización de p menos uno es a lo sumo B. Estudiantes de teoría de números elemental, competidores de CTF y aprendices de criptografía encuentran este algoritmo al estudiar por qué los módulos RSA deben evitar primos con totientes suaves. Esta capacidad ejecuta una búsqueda determinista de etapa uno de Pollard p−1: construye el producto de potencias primas hasta B, eleva una base pequeña a ese exponente módulo n y devuelve el mcd de esa potencia menos uno con n cuando el mcd es un factor propio.

Cómo Pollard p−1 halla un factor a partir de un p−1 suave

Fije un entero compuesto n y una cota de suavidad positiva B. La observación de Pollard es sencilla: si p es un divisor primo de n y toda potencia prima que divide a p menos uno es a lo sumo B, entonces el mínimo común múltiplo de los enteros del uno al B es múltiplo de p menos uno.

Por el pequeño teorema de Fermat, cualquier base a coprima con p cumple que a elevado a p menos uno es congruente con uno módulo p, y por tanto a elevada a ese gran mcm también es congruente con uno módulo p. Calcular la misma potencia módulo n y tomar el máximo común divisor del resultado menos uno con n suele producir p u otro factor no trivial.

En la práctica la implementación nunca construye el mcm completo de forma explícita; criba los primos hasta B y, para cada primo q, eleva el acumulador en curso a la mayor potencia de q que no supere B, todo módulo n. Tras cada paso de potencia prima evalúa el mcd del acumulador menos uno con n. Un mcd intermedio no trivial se devuelve de inmediato.

Si el mcd colapsa a n, un recorrido de recuperación más fino sobre exponentes menores intenta aislar un solo factor primo antes de abandonar esa base. Se prueban varias bases pequeñas para que órdenes desafortunados de la base dos no oculten un factor que de otro modo sería B-suave. El método no es un algoritmo de factorización completa: devuelve un factor no trivial y el cofactor correspondiente.

Quien necesite la factorización prima completa puede alimentar cada pieza compuesta a una herramienta de factorización en primos o subir B y volver a ejecutar. El éxito solo está garantizado en el escenario de p−1 suave; factores primos grandes de p menos uno obligan a una B mayor o a otro algoritmo, como el método de curvas elípticas o la criba cuadrática.

Cuándo conviene este método de factorización

Los cursos de criptografía usan Pollard p−1 para mostrar por qué los primos con predecesores suaves son peligrosos al generar parámetros RSA y Diffie–Hellman; una herramienta en vivo que acepta n y B permite al instructor demostrar una división en clase sin escribir a mano la potenciación modular.

Las plataformas CTF y de tareas necesitan un oráculo determinista que o bien devuelva un factor documentado para semiprimos clásicos como mil tres con cota dieciséis, o bien rechace cotas demasiado pequeñas para que los correctores puedan marcar tanto factores correctos como razonamientos de fallo correctos. Los ingenieros de seguridad que auditan generación de claves heredada pueden cribar módulos candidatos en busca de factores con p−1 suave antes de que lleguen a producción.

Autores de notebooks que ya tienen una rutina general de factorización en primos aún se benefician de un extremo p−1 explícito cuando la lección es el método en sí y no la lista completa de factores. Mantenga n dentro del límite de dígitos, elija B lo bastante grande para cubrir el mayor factor primo de p menos uno de algún primo p que divida n, y obtendrá factores reproducibles para docencia, write-ups de CTF y auditorías ligeras sin montar un sistema completo de álgebra computacional.