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)
“Nothing ever prepares a couple for having a baby, especially the first one. And even baby number two or three, the surprises and challenges, the cosmic curve balls, keep on coming. We can’t believe how much children change everything—the time we rise and the time we go to bed; the way we fight and the way we get along. Even when, and if, we make love.”
—Susan Lapinski (20th century)
“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)