Choice of Parameters
Not every number is an appropriate choice for the SNFS: you need to know in advance a polynomial f of appropriate degree (the optimal degree is conjectured to be, which is 4, 5, or 6 for the sizes of N currently feasible to factorise) with small coefficients, and a value x such that where N is the number to factorise. There is an extra condition: x must satisfy for a and b no bigger than .
One set of numbers for which such polynomials exist are the numbers from the Cunningham tables; for example, when NFSNET factored 3^479+1, they used the polynomial x^6+3 with x=3^80, since (3^80)^6+3 = 3^480+3, and .
Numbers defined by linear recurrences, such as the Fibonacci and Lucas numbers, also have SNFS polynomials, but these are a little more difficult to construct. For example, has polynomial, and the value of x satisfies .
If you already know some factors of a large SNFS-number, you can do the SNFS calculation modulo the remaining part; for the NFSNET example above, 3^479+1 = (4*158071*7167757*7759574882776161031) times a 197-digit composite number (the small factors were removed by ECM), and the SNFS was performed modulo the 197-digit number. The number of relations required by SNFS still depends on the size of the large number, but the individual calculations are quicker modulo the smaller number.
Read more about this topic: Special Number Field Sieve
Famous quotes containing the words choice of, choice and/or parameters:
“The base of all artistic genius is the power of conceiving humanity in a new, striking, rejoicing way, of putting a happy world of its own creation in place of the meaner world of common days, of generating around itself an atmosphere with a novel power of refraction, selecting, transforming, recombining the images it transmits, according to the choice of the imaginative intellect. In exercising this power, painting and poetry have a choice of subject almost unlimited.”
—Walter Pater (1839–1894)
“...there are important considerations in the world beyond plain sewing and teaching dull little boys the alphabet. Any woman who has brains and willing hands finds twenty remunerative occupations open to her where formerly she would have found merely the inevitable two—plain sewing, or the dull little boys. All she had to do is to make her choice and then buckle on her armor of perseverance, while the world applauds.”
—Clara (Marquise)
“Men have defined the parameters of every subject. All feminist arguments, however radical in intent or consequence, are with or against assertions or premises implicit in the male system, which is made credible or authentic by the power of men to name.”
—Andrea Dworkin (b. 1946)