In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it.
The special number field sieve is efficient for integers of the form re ± s, where r and s are small (for instance Mersenne numbers).
Heuristically, its complexity for factoring an integer is of the form:
in O and L-notations.
The SNFS has been used extensively by NFSNet (a volunteer distributed computing effort), NFS@Home and others to factorise numbers of the Cunningham project; for some time the records for integer factorisation have been numbers factored by SNFS.
Read more about Special Number Field Sieve: Overview of Method, Details of Method, Choice of Parameters, Limitations of Algorithm
Famous quotes containing the words special, number, field and/or sieve:
“We’ve got to figure these things a little bit different than most people. Y’know, there’s something about going out in a plane that beats any other way.... A guy that washes out at the controls of his own ship, well, he goes down doing the thing that he loved the best. It seems to me that that’s a very special way to die.”
—Dalton Trumbo (1905–1976)
“Envy has blackened every page of his history.... The future, in its justice, will number him among those men whom passions and an excess of activity have condemned to unhappiness, through the gift of genius.”
—Eugène Delacroix (1798–1863)
“An enormously vast field lies between “God exists” and “there is no God.” The truly wise man traverses it with great difficulty. A Russian knows one or the other of these two extremes, but is not interested in the middle ground. He usually knows nothing, or very little.”
—Anton Pavlovich Chekhov (1860–1904)
“It’s like pushing marbles through a sieve. It means the sieve will never be the same again.”
—Before the 1972 Democratic Convention in Miami. As quoted in Crazy Salad, ch. 6, by Nora Ephron (1972)