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 rebellion is against time pollution, the feeling that the essence of what makes life worth living—the small moments, the special family getaways, the cookies in the oven, the weekend drives, the long dreamlike summers Mso much of this has been taken from us, or we have given it up. For what? Hitachi stereos? Club Med? Company cars? Racquetball? For fifteen-hour days and lousy day care?”
—Richard Louv (20th century)
“Computers are good at swift, accurate computation and at storing great masses of information. The brain, on the other hand, is not as efficient a number cruncher and its memory is often highly fallible; a basic inexactness is built into its design. The brain’s strong point is its flexibility. It is unsurpassed at making shrewd guesses and at grasping the total meaning of information presented to it.”
—Jeremy Campbell (b. 1931)
“Vigil strange I kept on the field one night;
When you my son and my comrade dropt at my side that day,
One look I but gave which your dear eyes return’d with a look I
shall never forget,
One touch of your hand to mine O boy, reach’d up as you lay on the ground,”
—Walt Whitman (1819–1892)
“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)