Criba especial del cuerpo de números

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 r e \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.

Referencia[editar]

  1. Actualmente no es más que una conjetura.
  2. Pomerance, Carl (diciembre 1996). «A Tale of Two Sieves». Notices of the AMS 43 (12):  pp. 1473-1485. http://www.ams.org/notices/199612/pomerance.pdf. Consultado el 14-3-2010.