Sobre supuestos de suavidad en factorización de enteros.

Question

Me he encontrado con muchos métodos de factorización y la mayoría de ellos parecen asumir la suavidad de algunos números.

Por ejemplo

1. Cuando$p-1$ es suave
2. Cuando$|E(\mathbb{F}_p)|$ es suave. (Factorización de la curva elíptica)
3. Suavidad de ideales primordiales en los tamices de campo numérico.

¿Quiero saber si se sabe que otras nociones son equivalentes a la factorización como la suavidad de$p+1$ o$p^2+1$?

Answer 1

Sí. No es la $p+1$ método descrito por Williams (1982) y un cyclotomic generalización por Bach, Shallit (1989).

Uno de los problemas con mayor grado cyclotomic polinomios es que sus valores crecen tan rápidamente que la densidad de suave valores por debajo de un cierto límite mucho inferior a la de la $p-1$ $p+1$ métodos.

Un problema general con la cyclotomic métodos, incluyendo la $p\pm1$, es que $p$ rígidamente determina el valor entero que se requiere para ser suave. Si no es suave, el método fallará, y reintentar no se puede esperar para ayudar, excepto, quizá, reintentando con una mayor suavidad obligado.

La elíptica de la curva de método, propuesto 1985 por H. W. Jr y Lenstra discuten pronto después de, por ejemplo, por Brent (1985), es menos limitada. El método tiene éxito si algunos elegidos al azar de curva elíptica pasa a tener lisa orden sobre el campo finito con $p$ elementos, pero ese orden no es fijo, por ejemplo,$p\pm1$, pero puede variar alrededor de $p+1$ en un intervalo de de ancho acerca de $4\sqrt{p}$, dependiendo de la curva elegida. Así que si falla, se puede tratar simplemente de otra curva y otra vez la esperanza de llegar a algunas de lisa valor de cerca de lo desconocido $p$ y por lo tanto tener éxito.

Por lo tanto, mayores cyclotomic métodos se encuentran rara vez en la práctica. Normalmente, los siguientes métodos son intentado:

1. Métodos para los más pequeños factores: la división de juicios, Rho de Pollard, ...
2. una ejecución de la $p-1$ método,
3. acerca de los tres intentos de la $p+1$ método (hay algunas adivinanzas de un adecuado rectangulares$\bmod{p}$, por lo tanto, un intento podría no ser suficiente),
4. un mayor número de carreras de la elíptica de la curva de método, cada uno con un recién elegido de la curva,
5. un número aún mayor de las curvas con el aumento de la suavidad de los límites,
6. Si es aplicable (es decir, si la longitud del número a tener en cuenta y la cantidad de potencia de cálculo disponible permite), la criba cuadrática o el campo de número de tamiz.

Feliz de factoring.