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:
“The experience and behaviour that gets labelled schizophrenic is a special strategy that a person invents in order to live in an unlivable situation.”
—R.D. (Ronald David)
“He is the greatest artist who has embodied, in the sum of his works, the greatest number of the greatest ideas.”
—John Ruskin (1819–1900)
“Yet, hermit and stoic as he was, he was really fond of sympathy, and threw himself heartily and childlike into the company of young people whom he loved, and whom he delighted to entertain, as he only could, with the varied and endless anecdotes of his experiences by field and river: and he was always ready to lead a huckleberry-party or a search for chestnuts and grapes.”
—Ralph Waldo Emerson (1803–1882)
“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)