Criba del campo de los números especiales

Criba del campo de los números especiales

Criba del campo de los números especiales

La criba especial de cuerpo de números especiales (en inglés special number field sieve, SNFS) es un algoritmo especializado de factorización en números primos. Cuando la frase “criba de cuerpo de números” se utiliza sin la mención especial o general, se refiere al GNFS, la criba general de cuerpo de números.

Su tiempo de ejecución y su complejidad en notación de Landau parece ser, en la notación de Landau,[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 las totalidades de la forma r e ± s, dónde 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ó el SNFS mucho y de otros para descomponer en factores los números del proyecto de Cunningham.

Referencia

  1. Actualmente, no es más que una conjetura.
  2. Pomerance, Carl (December 1996), "A Tale of Two Sieves", Notices of the AMS 43 (12): 1473-1485, http://www.ams.org/notices/199612/pomerance.pdf 
Obtenido de "Criba del campo de los n%C3%BAmeros especiales"

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW …   Wikipedia Español

  • Trillo (agricultura) — Para otros usos de este término, véase Trillo (desambiguación). Trillo, vista superior …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”