mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-01-07, 05:14   #1
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

354310 Posts
Default 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.
jasonp is offline   Reply With Quote
Old 2008-01-07, 08:44   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

24×13×53 Posts
Default

Quote:
Originally Posted by jasonp View Post
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
xilman is offline   Reply With Quote
Old 2008-01-07, 14:20   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

Quote:
Originally Posted by xilman View Post
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
jasonp is offline   Reply With Quote
Old 2008-01-07, 20:23   #4
dleclair
 
dleclair's Avatar
 
Mar 2003

7×11 Posts
Default

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
dleclair is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A surprising case of a new shiny thing being step-function better fivemack Astronomy 12 2017-01-24 17:49
Xyzzy, the man, the myth, the surprising but not disappointing reality jasong jasong 6 2016-04-26 22:41
Interesting but not surprising point-in-time stats petrw1 PrimeNet 3 2015-09-01 19:35
A bug or... a surprising result???... lycorn PrimeNet 20 2011-06-26 19:52
Surprising news headlines 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.