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 universal social pressure upon women to be all alike, and do all the same things, and to be content with identical restrictions, has resulted not only in terrible suffering in the lives of exceptional women, but also in the loss of unmeasured feminine values in special gifts. The Drama of the Woman of Genius has too often been a tragedy of misshapen and perverted power.”
—Anna Garlin Spencer (1851–1931)
“Strange goings on! Jones did it slowly, deliberately, in the bathroom, with a knife, at midnight. What he did was butter a piece of toast. We are too familiar with the language of action to notice at first an anomaly: the ‘it’ of ‘Jones did it slowly, deliberately,...’ seems to refer to some entity, presumably an action, that is then characterized in a number of ways.”
—Donald Davidson (b. 1917)
“You cannot go into any field or wood, but it will seem as if every stone had been turned, and the bark on every tree ripped up. But, after all, it is much easier to discover than to see when the cover is off. It has been well said that “the attitude of inspection is prone.” Wisdom does not inspect, but behold.”
—Henry David Thoreau (1817–1862)
“They went to sea in a Sieve, they did,
In a Sieve they went to sea:
In spite of all their friends could say,
On a winter’s morn, on a stormy day,”
—Edward Lear (1812–1888)