{G,GG,S}NFS

[Dubslow]

Originally Posted by em99010pepe

Here you have a Master thesis entitled "An Introduction to the General Number Field Sieve" where you can start learning about GNFS.
For more detail on the number field sieve (NFS) you can read one of the many introductory papers listed in the readme that comes with the msieve source.

Now get to work!

Thank you thank you thank you. I'm only through 5 pages and it's already starting to make a whole lot more sense! (LaurV! It's been mashed and puréed just to spoonfeed people like us!)

Edit: I need a place to ask questions, and until someone says otherwise this thread is as good as any. So: Am I right in thinking that since a given congruence of squares is not guaranteed to produce a factorization, that Dixon's method (i.e. finding a linear dependence) may need to be run more than once in case the corresponding congruence doesn't produce a factor?

[xilman]

Originally Posted by Dubslow

Thank you thank you thank you. I'm only through 5 pages and it's already starting to make a whole lot more sense! (LaurV! It's been mashed and puréed just to spoonfeed people like us!)

Edit: I need a place to ask questions, and until someone says otherwise this thread is as good as any. So: Am I right in thinking that since a given congruence of squares is not guaranteed to produce a factorization, that Dixon's method (i.e. finding a linear dependence) may need to be run more than once in case the corresponding congruence doesn't produce a factor?

Correct. Assuming you are trying to factor a product of two distinct primes, any of NFS, QS, CFRAC, Dixon, etc has a 50% chance of finding the trivial factorization.

[Dubslow]

Originally Posted by xilman

Correct. Assuming you are trying to factor a product of two distinct primes, any of NFS, QS, CFRAC, Dixon, etc has a 50% chance of finding the trivial factorization.

Somebody should tell the author -- he says 1/3.

If one is able to produce random integers x and y that satisfy (1.1), how likely is it that
gcd(x + y ; n) or gcd(x − y ; n) is a non-trivial factor of n? In the case where n is the product
of two distinct primes p and q, such as when n is a modulus used in the RSA method of
x1.1, it turns out that a non-trivial factor of n is extracted in 2=3 of the cases, as seen in
Table 1.1.

Also, I *think* I understand the quadratic sieve (having finished page 6). It's actually not-too-terribly-difficult to understand. (The terrifying part is that I still don't understand any of the NFS terminology, which means it's *not* an simple extension/optimization of the QS...) Edit: The Wikipedia page says that the 'actual' poly used in QS is y(x)=(ceiling(sqrt(n)) + x)^2 - n, as opposed to the y(x)=x^2-n given in the linked paper. I'm guessing that the former is what's actually done in YAFU/Msieve?

[xilman]

Originally Posted by Dubslow

Somebody should tell the author -- he says 1/3.

Take a careful look at that table from which he draws the 1/3 conclusion. Why are there only 9 rows in it?

[R.D. Silverman]

Originally Posted by xilman

Correct. Assuming you are trying to factor a product of two distinct primes, any of NFS, QS, CFRAC, Dixon, etc has a 50% chance of finding the trivial factorization.

Correct. Sort of.

This is mis-worded. Rather than "any of NFS, QS, CFRAC, ......." it should
say "any given congruence of squares that arises in NFS, QS ...."

Saying just "Any of NFS, QS, CFRAC" etc. gives the impression that when
the algorithm is run, there is a 50% chance of success. This is false.
One gets multiple congruences of squares and each one has a 50%
chance of success. If there are k such congruences, the chance that they
all fail is 1/2^k.

i.e. for each congruence A^2 = B^2 mod N there is a 50% chance of
success assuming that N is the product of two primes.

Note that if N has more than two factors the probability increases.
Indeed. If N has k distinct prime factors, the probability of success
per congruence is 1 - 1/2^(k-1).

Hint: consider the congruence modulo each of the prime factors of N.
then apply the Chinese Remainder Theorem to the product of the primes.

To see where the 50% comes from:

For A^2 = q mod p, p prime, there are two solutions.
For A^2 = B^2 mod p there are 4: two choices each for A and B.
But of these 4 exactly two are trivial: A=B or A=-B (mod p).

[xilman]

Originally Posted by R.D. Silverman

Correct. Sort of.

This is mis-worded. Rather than "any of NFS, QS, CFRAC, ......." it should
say "any given congruence of squares that arises in NFS, QS ...."

Thank you, it was very sloppy phrasing on my part.


Paul

[bsquared]

Originally Posted by Dubslow

Also, I *think* I understand the quadratic sieve (having finished page 6). It's actually not-too-terribly-difficult to understand. (The terrifying part is that I still don't understand any of the NFS terminology, which means it's *not* an simple extension/optimization of the QS...) Edit: The Wikipedia page says that the 'actual' poly used in QS is y(x)=(ceiling(sqrt(n)) + x)^2 - n, as opposed to the y(x)=x^2-n given in the linked paper. I'm guessing that the former is what's actually done in YAFU/Msieve?

YAFU/msieve both use the self-initializing quadratic sieve, which uses the polynomial g(x) = (ax + b)^2 - N, where b^2 - N = ac. One of the best papers describing this variant of QS (and comparing it to the original method) is this one. I referred to it constantly when implementing YAFU's QS.

[jasonp]

bsquared's g(x) above is not actually different from the 'basic' QS polynomial, it just explicitly samples the one QS polynomial at very widely spaced points on the arithmetic progression ax+b, and the constants 'a' and 'b' are chosen so that g(x) is always divisible by 'a' for every x, leaving a cofactor that is smaller and thus more likely to yield a good relation during sieving.

Contini's paper is one of very few that give all the low-level details for implementing SIQS.