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:
“At birth man is offered only one choice—the choice of his death. But if this choice is governed by distaste for his own existence, his life will never have been more than meaningless.”
—Jean-Pierre Melville (1917–1973)
“Once women begin to question the inevitability of their subordination and to reject the conventions formerly associated with it, they can no longer retreat to the safety of those conventions. The woman who rejects the stereotype of feminine weakness and dependence can no longer find much comfort in the cliché that all men are beasts. She has no choice except to believe, on the contrary, that men are human beings, and she finds it hard to forgive them when they act like animals.”
—Christopher Lasch (b. 1932)
“What our children have to fear is not the cars on the highways of tomorrow but our own pleasure in calculating the most elegant parameters of their deaths.”
—J.G. (James Graham)