Pollard p-1 Algorithm
Método p-1 de Pollard: si un factor primo p tiene un p-1 B-suave, entonces un mcd que implica a^(B!) mod n revela el factor.
Propósito
Factorizar números de ciertas formas usando una suposición de suavidad; un algoritmo de factorización temprano.
Mecanismo
Se elige una cota B y se calcula M=∏(q^e ≤ B con q primo), luego a=a^M mod n. Si p|n y p-1 es B-suave, entonces a≡1 (mod p), y mcd(a-1,n) da p. Si falla, se aumenta B.
Casos de uso
- Factorización de enteros
- Algoritmos de teoría de números
- Criptoanálisis
Herramientas relacionadas
Calculadora de divisores
Factor Calculator — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor. HERRAMIENTA
Verificador de números primos
Prime Checker — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor. HERRAMIENTA
Factorización Pollard p-1
Pollard p-1 Factorization — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor. HERRAMIENTA