20090105, 15:58  #1 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
2^{7}×47 Posts 
Msieve QS estimates
i have been collecting data from msieve logs and i think that i should be able to predict how many full, combined and partial relations the factorization will use and thus how far a factorization is complete as full and partial relations are produced at a linear rate
estimates for my own factorizations have been quite accurate but i would like to test this a few more times could a couple of people post a number of digits and the leading digit and i will try an estimate after i have made the estimate could you post the msieve.log so we can see how accurate i have been 
20090105, 16:05  #2 
"Ben"
Feb 2007
3×17×73 Posts 
I've done a rough estimate for YAFU as well, valid for numbers big enough to use the double large prime variation only. In that case you should need roughly 328.813402*EXP(0.084148*num_digits) partial relations.
As for your msieve test, here is the largest job I've done using msieve: number of digits: 100 leading 2 digits: 18... 
20090105, 16:31  #3  
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
2^{7}×47 Posts 
Quote:
i have data for a 99 digit and a 102 digit based on these 23000 full relations 76000 combined relations 1.5M partial relations edit: i will also have a matrix of size 93000^2 with weight ~52/col although the weight is a bit unpredictable in future could i have the number of needed relations Last fiddled with by henryzz on 20090105 at 16:38 

20090105, 16:50  #4  
"Ben"
Feb 2007
E8B_{16} Posts 
Quote:
Code:
Mon Dec 1 20:50:35 2008 Msieve v. 1.38 Mon Dec 1 20:50:35 2008 random seeds: 8e9dc914 9bc0df64 Mon Dec 1 20:50:35 2008 factoring 1802716097522165018257858828415111497060066282677325501816640492782221110851604465066510547671104729 (100 digits) Mon Dec 1 20:50:36 2008 no P1/P+1/ECM available, skipping Mon Dec 1 20:50:36 2008 commencing quadratic sieve (100digit input) Mon Dec 1 20:50:36 2008 using multiplier of 1 Mon Dec 1 20:50:36 2008 using 32kb Intel Core sieve core Mon Dec 1 20:50:36 2008 sieve interval: 36 blocks of size 32768 Mon Dec 1 20:50:36 2008 processing polynomials in batches of 6 Mon Dec 1 20:50:36 2008 using a sieve bound of 2681729 (97602 primes) Mon Dec 1 20:50:36 2008 using large prime bound of 402259350 (28 bits) Mon Dec 1 20:50:36 2008 using double large prime bound of 3076883377187400 (4352 bits) Mon Dec 1 20:50:36 2008 using trial factoring cutoff of 52 bits Mon Dec 1 20:50:36 2008 polynomial 'A' values have 13 factors Tue Dec 2 03:53:25 2008 97944 relations (23379 full + 74565 combined from 1470172 partial), need 97698 Tue Dec 2 03:53:29 2008 begin with 1493551 relations Tue Dec 2 03:53:29 2008 reduce to 258579 relations in 11 passes Tue Dec 2 03:53:29 2008 attempting to read 258579 relations Tue Dec 2 03:53:31 2008 recovered 258579 relations Tue Dec 2 03:53:31 2008 recovered 247905 polynomials Tue Dec 2 03:53:32 2008 attempting to build 97944 cycles Tue Dec 2 03:53:32 2008 found 97944 cycles in 6 passes Tue Dec 2 03:53:32 2008 distribution of cycle lengths: Tue Dec 2 03:53:32 2008 length 1 : 23379 Tue Dec 2 03:53:32 2008 length 2 : 16651 Tue Dec 2 03:53:32 2008 length 3 : 16413 Tue Dec 2 03:53:32 2008 length 4 : 13382 Tue Dec 2 03:53:32 2008 length 5 : 10169 Tue Dec 2 03:53:32 2008 length 6 : 6933 Tue Dec 2 03:53:32 2008 length 7 : 4669 Tue Dec 2 03:53:32 2008 length 9+: 6348 Tue Dec 2 03:53:32 2008 largest cycle: 21 relations Tue Dec 2 03:53:32 2008 matrix is 97602 x 97944 (26.9 MB) with weight 6276535 (64.08/col) Tue Dec 2 03:53:32 2008 sparse part has weight 6276535 (64.08/col) Tue Dec 2 03:53:33 2008 filtering completed in 3 passes Tue Dec 2 03:53:33 2008 matrix is 93704 x 93768 (25.9 MB) with weight 6028303 (64.29/col) Tue Dec 2 03:53:33 2008 sparse part has weight 6028303 (64.29/col) Tue Dec 2 03:53:34 2008 saving the first 48 matrix rows for later Tue Dec 2 03:53:34 2008 matrix is 93656 x 93768 (14.9 MB) with weight 4544268 (48.46/col) Tue Dec 2 03:53:34 2008 sparse part has weight 2976114 (31.74/col) Tue Dec 2 03:53:34 2008 matrix includes 64 packed rows Tue Dec 2 03:53:34 2008 using block size 37507 for processor cache size 4096 kB Tue Dec 2 03:53:35 2008 commencing Lanczos iteration Tue Dec 2 03:53:35 2008 memory use: 14.2 MB Tue Dec 2 03:54:08 2008 lanczos halted after 1482 iterations (dim = 93655) Tue Dec 2 03:54:08 2008 recovered 16 nontrivial dependencies Tue Dec 2 03:54:08 2008 prp50 factor: 38589340584901213653958931179714585367490014795273 Tue Dec 2 03:54:08 2008 prp50 factor: 46715390058453362424711065024780497160328505582673 Tue Dec 2 03:54:08 2008 elapsed time 07:03:33 

20090105, 17:11  #5 
Jan 2009
Bilbao, Spain
283_{10} Posts 
I have datas for 108 digits (7), 110(1), 111(2) and 112(2 numbers), if you like.
Best. 
20090105, 18:46  #6  
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
2^{7}·47 Posts 
Quote:
in future my guess for 100 digits will be based on what you posted qs factorizations of the same size seem to have similar proportions of combined to full the only downside to this method is you have to collect quite a bit of data once i have finished combining my data into one file i will post it here 

20090105, 19:06  #7  
"Ben"
Feb 2007
7213_{8} Posts 
Quote:


20090105, 20:39  #8 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
2^{7}×47 Posts 

20090105, 20:42  #9 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
6016_{10} Posts 

20090105, 21:06  #10  
"Ben"
Feb 2007
3×17×73 Posts 
Quote:
Create a chart, from chart menu select add trendline, create a new exponential fit, and don't forget to select "display equation on chart" under the options tab. I have some more data for C60 < N < C100. I'll post later tonight. It might not work well if you mix all the data though, because msieve only turns on DLP at 85 digits in size, and the relation accumlation rate (and final full/partial ratio) changes quite a bit at that point.  ben. 

20090105, 22:46  #11 
Jan 2009
Bilbao, Spain
283 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Using msieve with c  burrobert  Msieve  9  20121026 22:46 
P1 B2 time estimates  henryzz  GMPECM  8  20091231 17:51 
GNFS estimates  10metreh  Factoring  48  20090408 01:54 
Chebyshev's Estimates  brownkenny  Math  2  20090122 17:21 
Accuracy of completion date estimates?  kdq  Software  4  20081004 05:02 