Criba especial del cuerpo de números

La criba especial del cuerpo de números (en inglés special number field sieve, SNFS) es un algoritmo especializado de factorización de números enteros. La criba (general) del cuerpo de números (GNFS) es una versión generalizada de este algoritmo que trata con números de todo tipo.

Su tiempo de ejecución y complejidad en notación de Landau parece ser:^[1]^[2]

\Theta \left(\exp \left(\left({\frac {32}{9}}n\right)^{\frac {1}{3}}(\log n)^{\frac {2}{3}}\right)\right).

La criba especial de cuerpo de números es eficaz para los números de la forma $re\pm s$ , donde $r$ y $s$ son pequeños. Se recomienda pues especialmente para descomponer en factores los números de Fermat y los números de Mersenne. NFSNET utilizó la SNFS mucho y de otros para descomponer en factores los números del proyecto de Cunningham.

Referencias editar

↑ Actualmente no es más que una conjetura.
↑ Pomerance, Carl (diciembre de 1996). «A Tale of Two Sieves». Notices of the AMS 43 (12): 1473-1485. Consultado el 14 de marzo de 2010.

Datos: Q655079

[1] Actualmente no es más que una conjetura.

[2] Pomerance, Carl (diciembre de 1996). «A Tale of Two Sieves». Notices of the AMS 43 (12): 1473-1485. Consultado el 14 de marzo de 2010.

[1]

[2]