Msieve QS estimates

henryzz · 2009-01-05, 15:58

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

bsquared · 2009-01-05, 16:05

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

henryzz · 2009-01-05, 16:31

Quote:

Originally Posted by bsquared

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

i should have mentioned my data becomes much more sparse for higher digits
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

bsquared · 2009-01-05, 16:50

Quote:

Originally Posted by henryzz

i should have mentioned my data becomes much more sparse for higher digits
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

Pretty close!

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 P-1/P+1/ECM available, skipping
Mon Dec 1 20:50:36 2008 commencing quadratic sieve (100-digit 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 (43-52 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

If all continues to go well, do you plan on posting your estimate method?

mataje · 2009-01-05, 17:11

I have datas for 108 digits (7), 110(1), 111(2) and 112(2 numbers), if you like.
Best.

henryzz · 2009-01-05, 18:46

Quote:

Originally Posted by bsquared

Pretty close!

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 P-1/P+1/ECM available, skipping
Mon Dec 1 20:50:36 2008 commencing quadratic sieve (100-digit 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 (43-52 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

If all continues to go well, do you plan on posting your estimate method?

my method is simply make a guess based on previous factorizations that i have the log for
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

bsquared · 2009-01-05, 19:06

Quote:

Originally Posted by henryzz

my method is simply make a guess based on previous factorizations that i have the log for
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

Once you have a bunch of data, it should fit fairly well to an exp function as well.

henryzz · 2009-01-05, 20:39

Quote:

Originally Posted by bsquared

Once you have a bunch of data, it should fit fairly well to an exp function as well.

i have loads of data for up to 60 digits but i need more for higher digits
what program did you use to generate your formula

henryzz · 2009-01-05, 20:42

Quote:

Originally Posted by mataje

I have datas for 108 digits (7), 110(1), 111(2) and 112(2 numbers), if you like.
Best.

brilliant could you attach them in a zip here

bsquared · 2009-01-05, 21:06

Quote:

Originally Posted by henryzz

i have loads of data for up to 60 digits but i need more for higher digits
what program did you use to generate your formula

Excel.

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.

mataje · 2009-01-05, 22:46

Quote:

Originally Posted by henryzz

brilliant could you attach them in a zip here

Done.

2009-01-05, 15:58	#1
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 37×163 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Using msieve with c	burrobert	Msieve	9	2012-10-26 22:46
P-1 B2 time estimates	henryzz	GMP-ECM	8	2009-12-31 17:51
GNFS estimates	10metreh	Factoring	48	2009-04-08 01:54
Chebyshev's Estimates	brownkenny	Math	2	2009-01-22 17:21
Accuracy of completion date estimates?	kdq	Software	4	2008-10-04 05:02

2009-01-05, 16:05	#2
bsquared "Ben" Feb 2007 7223₈ 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.813402EXP(0.084148num_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...

2009-01-05, 17:11	#5
mataje Jan 2009 Bilbao, Spain 433₈ Posts	I have datas for 108 digits (7), 110(1), 111(2) and 112(2 numbers), if you like. Best.