20090101, 10:37  #1 
Aug 2006
Monza, Italy
2^{2}·3·5 Posts 
Oversieving + estimate of relations needed
I just installed a new quadcore machine along with my old dualcore so I tried to run 6 instances of msieve on a test C104 during the night. All went pretty well but when I merged the .dat files I found that the number of combined relations was way too high (around 10x) and the algebra failed giving me the odd "only trivial relations found" error already discussed in a previous thread. So my questions are:
1) has this behaviour been investigated more, and are there any plans to "fix" it? Or maybe it already was and I just did something wrong? 2) Is there a way to estimate the number of relations needed on a distributed job so that it is possible to stop it with r (which I assume stops at the relevant number of full+combined relations)? Thank you for your time. 
20090101, 16:47  #2 
Tribal Bullet
Oct 2004
110111001001_{2} Posts 
This is a known problem, and both QS and NFS have a surprising amount of trouble dealing with a dataset that contains enormously too many relations. With msieve, the NFS code is much more robust when that happens, but the QS code is almost defenseless against it.
Factorizations that are about the same size will need about the same number of partial relations for the postprocessing to work, but nobody has catalogued what that target number should be, and nobody has automatic means to run multiple sieving instances and stop when the total relations found hits that target. 
20090101, 17:21  #3 
Mar 2007
Austria
2·151 Posts 
Why not simply delete/ignore the relations that are too much?
nugget 
20090101, 19:23  #4 
Aug 2006
Monza, Italy
2^{2}×3×5 Posts 
Jason: Thank you. I thought we might reach a rough estimate based on the theory easily enough but obviously it's not that easy.
Nugget: If I knew how many of them are too much, I would certainly do it. But in (say) this case we have 6 files combined, and we don't know what is the threshold that triggers the "bug". So how many files should I use? I could try with 2 and they might not be enough, and with 3 the bug might appear. So i might use only half of the third file and so on... not very practical, as you can see, it would just be trial and error. Last fiddled with by RedGolpe on 20090101 at 19:27 
20090101, 22:04  #5 
Tribal Bullet
Oct 2004
DC9_{16} Posts 
Trial and error is what people seem to use now. At C104 size you should probably try somewhere around 34 million relations; the minimum number actually depends more on the size of large primes than the size of the input number.
Maybe I should modify the code to take the number of relations desired as an input parameter, to save everyone from having to reconstruct the savefile every time to have fewer and fewer relations. The code used to take that parameter but it was removed for some reason. Last fiddled with by jasonp on 20090101 at 22:06 
20090102, 02:31  #6  
Jun 2003
Ottawa, Canada
7·167 Posts 
Quote:
Jeff. 

20090615, 10:32  #7 
Aug 2006
Monza, Italy
2^{2}·3·5 Posts 
I am running some experiments with different sized composites and I will post the results here for everyone's benefit.
Input = Approximate size of composite to crack. Need = Number of relations needed. Full = Number of full relations found when result is output. Part = Number of partial relations found when result is output. Code:
Input Need Full Part  10^60 3.0k 1.4k 15k 10^70 10k 4.6k 58k 10^80 50k 25k 274k Last fiddled with by RedGolpe on 20090615 at 10:35 
20090615, 12:28  #9  
Nov 2003
2^{2}×5×373 Posts 
Quote:
Given the size of the numbers, I assume you are discussing QS. I discussed all of this and more over 20 years ago in my 1987 Math. Comp. paper 

20090615, 12:57  #10 
Aug 2006
Monza, Italy
2^{2}·3·5 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Oversieving  chris2be8  Msieve  7  20100313 21:51 
v1.40 patch for massive NFS oversieving  jasonp  Msieve  18  20090409 03:20 
Extreme oversieving and msieve  jbristow  Msieve  8  20080102 21:43 
Oversieving in msieve  fivemack  Msieve  1  20070928 18:26 
More relations mean many more relations wanted  fivemack  Factoring  7  20070804 17:32 