Algoritmo de factorización de grupos algebraicos

A menudo es posible multiplicar un elemento de grupo por varios enteros pequeños más rápidamente que por su producto, generalmente mediante métodos basados ​​en diferencias: se calculan las diferencias entre primos consecutivos y se suman consecutivamente por . Esto significa que un procedimiento de dos pasos se vuelve sensato, primero calculando Ax multiplicando x por todos los primos por debajo de un límite B ₁ , y luego examinando p Ax para todos los primos entre B ₁ y un límite mayor B ₂ . Esto relajaría el requisito de suavidad para el orden del grupo de ser B ₁ -potencia suave a ser el producto de un primo entre B ₁ y B ₂ y un número B ₁ -potencia suave.${\displaystyle d_{i}r}$

El método basado en diferencias es el método básico de "etapa 2". Existen modificaciones como el emparejamiento de primos de Montgomery (1978) y la extensión de Brent-Suyama. ^{[ 2 ]}

Un método de "etapa 2" más eficiente utiliza la multiplicación de polinomios implementada mediante la transformada rápida de Fourier . Este método fue demostrado originalmente para el ECM de Lenstra por Montgomery en 1992, ^{[ 3 ]} pero desde entonces se ha adaptado para p -1 y p +1. ^{[ 2 ]}

Si el grupo algebraico es el grupo multiplicativo módulo N , las identidades unilaterales se reconocen calculando los máximos divisores comunes con N , y el resultado es el método p − 1   .

Si el grupo algebraico es el grupo multiplicativo de una extensión cuadrática de N , el resultado es el método p  +  1 ; el cálculo implica pares de números módulo N. No es posible saber si es realmente una extensión cuadrática de sin conocer la factorización de N. Esto requiere saber si t es un residuo cuadrático módulo N , y no se conocen métodos para hacer esto sin conocer la factorización. Sin embargo, siempre que N no tenga un número muy grande de factores, en cuyo caso se debería usar primero otro método, elegir un t aleatorio (o mejor dicho, elegir ^A con t = A² − 4 ) dará accidentalmente con bastante rapidez un no residuo cuadrático. Si t es un residuo cuadrático, el método p + 1 degenera en una forma más lenta del método p − 1.${\displaystyle \mathbb {Z} /N\mathbb {Z} [{\sqrt {t}}]}$${\displaystyle \mathbb {Z} /N\mathbb {Z} }$    

Si el grupo algebraico es una curva elíptica , las identidades unilaterales se pueden reconocer por la falta de inversión en el procedimiento de adición de puntos de la curva elíptica, y el resultado es el método de la curva elíptica ; el teorema de Hasse establece que el número de puntos en una curva elíptica módulo p siempre está dentro de p .${\displaystyle 2{\sqrt {p}}}$

Los tres grupos algebraicos anteriores son utilizados por el paquete GMP-ECM, ^{[ 4 ]} que incluye implementaciones eficientes del procedimiento de dos etapas y una implementación del algoritmo de exponenciación de grupo PRAC que es bastante más eficiente que el enfoque de exponenciación binaria estándar .

En ocasiones se propone el uso de otros grupos algebraicos —extensiones de orden superior de N o grupos correspondientes a curvas algebraicas de género superior—, pero casi siempre resulta impracticable. Por ejemplo, se puede utilizar la variedad jacobiana de una curva hiperelíptica , que posee una ley de grupo eficiente. Estos métodos terminan imponiendo restricciones de suavidad a números del orden de p ^d para algún d  >  1, que tienen muchas menos probabilidades de ser suaves que los números del orden de p .

La primera etapa ingenua utiliza operaciones de bits, mientras que la primera etapa que solo utiliza potencias de números primos toma , donde N es el número a factorizar y denota el costo de multiplicar dos enteros de x bits (prácticamente utilizando métodos basados ​​en FFT). ^{[ 1 ]}${\displaystyle O(B_{1}\log(B_{1})M(\log(N)))}$${\displaystyle O(B_{1}M(\log(N)))}$${\displaystyle M(x)}$${\displaystyle M(\log(N))=O(N\log(N)\log \log(N))}$

La segunda etapa estándar (basada en diferencias) utiliza operaciones de bits. ^{[ 1 ]} La segunda etapa basada en polinomios utiliza operaciones de bits (el término puede descartarse asumiendo , lo cual suele ser el caso). Variar el tamaño de la convolución ofrece una compensación entre memoria y espacio: por cada duplicación del uso de memoria, se puede duplicar la cantidad de avance en para la misma cantidad de cálculo. ^{[ 2 ]}${\displaystyle O((B_{2}-B_{1})M(\log(N)))}$${\displaystyle O({\sqrt {B_{2}-B_{1}}}\log(B_{2}-B_{1})M(\log(N)))}$${\displaystyle B_{1}}$${\displaystyle B_{2}>>B_{1}}$${\displaystyle B_{2}}$

Véase Kruppa (2010), secciones 5.3 y 5.4. ^{[ 5 ]}