mersenneforum.org A surprising result on QS/NFS matrix size
 Register FAQ Search Today's Posts Mark Forums Read

 2008-01-07, 05:14 #1 jasonp Tribal Bullet     Oct 2004 354310 Posts A surprising result on QS/NFS matrix size 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.
2008-01-07, 08:44   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

24×13×53 Posts

Quote:
 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

2008-01-07, 14:20   #3
jasonp
Tribal Bullet

Oct 2004

3×1,181 Posts

Quote:
 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.

Last fiddled with by jasonp on 2008-01-07 at 14:22

 2008-01-07, 20:23 #4 dleclair     Mar 2003 7×11 Posts 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 Last fiddled with by dleclair on 2008-01-07 at 20:25 Reason: tpyo

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Astronomy 12 2017-01-24 17:49 jasong jasong 6 2016-04-26 22:41 petrw1 PrimeNet 3 2015-09-01 19:35 lycorn PrimeNet 20 2011-06-26 19:52 dsouza123 Soap Box 2 2007-06-26 21:41

All times are UTC. The time now is 04:32.

Wed Dec 1 04:32:01 UTC 2021 up 130 days, 23:01, 1 user, load averages: 1.27, 1.25, 1.26