**Navigation**

Topics | Register • News • History • How to • Sequences statistics • Template prototypes |

# Difference between revisions of "Special number field sieve"

m |
(shortcut) |
||

Line 1: | Line 1: | ||

− | The '''special number field sieve''' | + | {{Shortcut|SNFS|Special number field sieve: special-purpose [[factorization]] algorithm.}} |

+ | The '''special number field sieve (SNFS)''' is a special-purpose [[factorization]] algorithm. The [[general number field sieve]] (GNFS) was derived from it. | ||

The special number field sieve is efficient for integers of the form ''r''<sup>''e''</sup> ± ''s'', where ''r'' and ''s'' are small. In particular, it is ideal for factoring [[Mersenne number]]s. | The special number field sieve is efficient for integers of the form ''r''<sup>''e''</sup> ± ''s'', where ''r'' and ''s'' are small. In particular, it is ideal for factoring [[Mersenne number]]s. | ||

Line 15: | Line 16: | ||

==External links== | ==External links== | ||

− | *[[Wikipedia:Special number field sieve|Special number field sieve]] | + | *[[Wikipedia:Special number field sieve|Special number field sieve]] |

*[http://sourceforge.net/projects/ggnfs GGNFS], developed by Chris Monico, containing Kleinjung/Franke polynomial selection and Jens Franke's lattice siever. | *[http://sourceforge.net/projects/ggnfs GGNFS], developed by Chris Monico, containing Kleinjung/Franke polynomial selection and Jens Franke's lattice siever. | ||

*[https://sourceforge.net/projects/msieve Msieve], developed by Jason Papadopoulos, having sophisticated postprocessing. | *[https://sourceforge.net/projects/msieve Msieve], developed by Jason Papadopoulos, having sophisticated postprocessing. | ||

*[http://cado-nfs.gforge.inria.fr/ CADO-NFS] on INRIA. | *[http://cado-nfs.gforge.inria.fr/ CADO-NFS] on INRIA. | ||

[[Category:Factorization]] | [[Category:Factorization]] |

## Latest revision as of 12:07, 19 February 2019

The **special number field sieve (SNFS)** is a special-purpose factorization algorithm. The general number field sieve (GNFS) was derived from it.

The special number field sieve is efficient for integers of the form *r*^{e} ± *s*, where *r* and *s* are small. In particular, it is ideal for factoring Mersenne numbers.

Its running time, in asymptotic notation, is conjectured to be:

- [math]\displaystyle{ \Theta\left(\exp\left( \left(\frac{32}{9}n\right)^{\frac{1}{3}} (\log n)^{\frac{2}{3}} \right)\right). }[/math]

The SNFS has been used extensively by NFSNET (a volunteer distributed computing effort) and others to factorise numbers of the Cunningham project.

The first step is the polynomial selection.

## See also

## External links

- Special number field sieve
- GGNFS, developed by Chris Monico, containing Kleinjung/Franke polynomial selection and Jens Franke's lattice siever.
- Msieve, developed by Jason Papadopoulos, having sophisticated postprocessing.
- CADO-NFS on INRIA.