A surprising result on QS/NFS matrix size

[jasonp]

This paper, if I read it correctly, claims that for the quadratic sieve with a factor base containing L primes, collecting L^x relations is enough to produce a nontrivial linear dependency with high probability, for x > 1/e.

I didn't think this was possible; the above says you only need a number of relations equal to about the cube root of the factor base size before expecting a dependency. The model doesn't assume handling large primes, and maybe that spoils everything in the real world, but it still sounds too good to be true. The paper says it's an inappropriate model for the quadratic sieve, but I can't see why...

This apparently started out as some kind of undergrad research project, which noticed something resembling the above via computational experiment.

[xilman]

Originally Posted by jasonp

This paper, if I read it correctly, claims that for the quadratic sieve with a factor base containing L primes, collecting L^x relations is enough to produce a nontrivial linear dependency with high probability, for x > 1/e.

I didn't think this was possible; the above says you only need a number of relations equal to about the cube root of the factor base size before expecting a dependency. The model doesn't assume handling large primes, and maybe that spoils everything in the real world, but it still sounds too good to be true. The paper says it's an inappropriate model for the quadratic sieve, but I can't see why...

This apparently started out as some kind of undergrad research project, which noticed something resembling the above via computational experiment.

The old rule of thumb, which I've been using for many years, is that 0.8(pi(LPB1)+pi(LPB2)) relations is sufficient, where LBPi is the large prime bound on each side.

The ROT works extremely well, but 0.8 is substantially larger than 1/e. If the claim was for 1-1/e for the exponent (about 0.63) the claim would be quite plausible, IMO. The ROT allows leeway for discarding excessively heavy relation-sets.

Pauil

[jasonp]

Originally Posted by xilman

The old rule of thumb, which I've been using for many years, is that 0.8(pi(LPB1)+pi(LPB2)) relations is sufficient, where LBPi is the large prime bound on each side.

The ROT works extremely well, but 0.8 is substantially larger than 1/e. If the claim was for 1-1/e for the exponent (about 0.63) the claim would be quite plausible, IMO. The ROT allows leeway for discarding excessively heavy relation-sets.

What's confisuing me is that their result is not a multiple of the number of factor base primes, it's a cube root of the number. i.e. a million factor base primes will have a dependency with only 100 matrix columns on average. This describes the original research.

[dleclair]

If I correctly understand the paper in the first link, it seems to say that if a matrix is built using the probability function that they list then it is likely to have a significant number of non-zero columns.

The function they chose gives the nth prime a 1/p chance of appearing in the nth column. So as a concrete example, bits in column 78498 have only a one-in-a-million chance of being set.

As a result it is not surprising that the resulting matrices have an extraordinary number of columns that are all zero and can be eliminated, thereby reducing the number of rows required.

This almost feels like complicated route arriving at the Prime Number Theorem ("the chance of a number N being prime is about 1 / ln(N), where ln(N) denotes the natural logarithm of N").

-Don