Por qué no se puede usar cyclotomic polinomios factorizar números grandes muy rápidamente?

Question

Dos simples palabras:

1. El polinomio $x^k-1$ puede ser factorised sobre los números enteros como un producto de (irreductible) cyclotomic polinomios: $$x^k-1 = \prod_{d|k}\Phi_d(x).$$ Si elegimos $k$ a ser un número que tiene una gran cantidad de divisores, a continuación, $x^k-1$ tendrá un montón de factores. Por ejemplo, si $k$ es un producto de $b$ distintos de los números primos, a continuación, $x^k-1$ ha $2^b$ factores.

2. Supongamos que tenemos algunos largeish número natural $n$, y queremos factorise ella. Una forma de encontrar un factor de $n$ sería para calcular el producto $a$ de los lotes de diferentes números de $a_i$, modulo $n,$ y, a continuación, calcular $\gcd(n, a)$. Si tenemos suerte y algunas de las $a_i$ son factores de $n$ pero $a$ no es un múltiplo de $n$, entonces el mcd será un no-trivial factor de $n$.

Poniendo a estos en conjunto, se puede imaginar que una buena manera de encontrar factores de $n$ sería para calcular $\gcd(n, x^k-1\mathrm{\ mod\ } n)$ con $k$ un producto de distintos números primos y $x>1$. Esto es equivalente a la prueba de $\Phi_d(x)$ por un factor común con $n$ para cada uno de los exponencialmente-muchos divisores $d|k$. Así que es posible que, ingenuamente, se espera que uno podría así factorise $n$ en el tiempo $O(\log n)$ o menos.

Por supuesto, esto no es realmente el trabajo uno no puede por lo tanto factorise números enormes en un abrir y cerrar de ojos. Me justificar esta afirmación sobre la no-matemáticos de la base de que a) si un método simple trabajó entonces alguien hubiera notado por ahora; y la heurística de los motivos que b) lo he probado, y no lo hizo.

Lo que me gustaría saber es por qué no funciona. Es de suponer que el problema es que el $2^b$ valores $\Phi_d(x)$ se distribuye en una suficientemente no-uniforme manera de bloquear el procedimiento. ¿Qué está pasando aquí?

No veo mucha sugerencia de esta falta de uniformidad en los ejemplos que son lo suficientemente pequeños para calcular todas las $\Phi_d(x)$ explícitamente en una cantidad de tiempo razonable. Por ejemplo, si $n=61\times71=4331$ e $k=9699690$ es el producto de los ocho primeros números primos, entonces la expresión $\Phi_d(2)$ es de 244 diferentes valores de $d$ rangos de la $2^8=256$ divisores de $k$. (Y como sucede, $\Phi_{35}(2)$ es un múltiplo de 71, y así computing $\gcd(4331, 2^{9699690}-1\mathrm{\ mod\ } 4331)$ revela la existencia de este factor.)

---

Agregado: Gracias a David E Speyer por una clara concisa respuesta. Acaba de hacer explícito, el "no-uniformidad" en juego aquí es que cada factor primo de $\Phi_d(x)$ es congruente con 1 módulo $d$.

Answer 1

Supongamos que estás en el escenario del peor caso: $N=pq$ donde $p=2p′+1$ e $q=2q′+1$ con $p$, $q$, $p′$ y $q′$ todos los primer y $p$ e $q$ aproximadamente del mismo tamaño. A continuación, el orden de $x$ modulo $p$ será $p′$ o $2p′$ cualquier $x \neq \pm 1 \mod p$, y del mismo modo modulo $q$. Así que esperamos que las $GCD(N,x^k−1)$ a ser trivial sólo si $p′$ o $q′$ brecha $k$. Las probabilidades de que esto ocurra son aproximadamente el $1/p′+1/q′ \approx 4/\sqrt{N}$, por lo que necesita para tratar de $\sqrt{N}$ valores de $(x,k)$ antes de esperar un éxito.

Answer 2

Cyclotomic el Factoring es una clase de la factorización de enteros de los algoritmos. Se basa en el de Euler congruencia $x^{\varphi(n)}-1 \equiv 0 \mod n$. Hay algunos bien conocidos casos especiales.

1. El $p-1$-Pollard algoritmo.
2. El $p+$-William algoritmo.

3. Aurifeuillian Factoring, este es el más antiguo.

   El momento en que la complejidad es $O(n^{1/4})$ de las operaciones aritméticas. Muchos autores han tratado de obtener $O(n^{1/5})$, pero no importante reducción en la complejidad que han alcanzado en las últimas décadas.

   Hay una gran cantidad de literatura sobre este tema, algunos están en la lista.

4. A. Granville, Aurifeuillian factores, Matemáticas Comp. Vol. 75, 2006.

5. E. Bach, Factoring con Cyclotomic Polinomios, Matemáticas. Comp. 1989.