mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2009-01-05, 15:58   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

7×857 Posts
Default 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
henryzz is offline   Reply With Quote
Old 2009-01-05, 16:05   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·919 Posts
Default

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...
bsquared is offline   Reply With Quote
Old 2009-01-05, 16:31   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

7×857 Posts
Default

Quote:
Originally Posted by bsquared View Post
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

Last fiddled with by henryzz on 2009-01-05 at 16:38
henryzz is offline   Reply With Quote
Old 2009-01-05, 16:50   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×919 Posts
Default

Quote:
Originally Posted by henryzz View Post
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?
bsquared is offline   Reply With Quote
Old 2009-01-05, 17:11   #5
mataje
 
mataje's Avatar
 
Jan 2009
Bilbao, Spain

283 Posts
Default

I have datas for 108 digits (7), 110(1), 111(2) and 112(2 numbers), if you like.
Best.
mataje is offline   Reply With Quote
Old 2009-01-05, 18:46   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

176F16 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
henryzz is offline   Reply With Quote
Old 2009-01-05, 19:06   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

367610 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
bsquared is offline   Reply With Quote
Old 2009-01-05, 20:39   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

7·857 Posts
Default

Quote:
Originally Posted by bsquared View Post
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 is offline   Reply With Quote
Old 2009-01-05, 20:42   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

7·857 Posts
Default

Quote:
Originally Posted by mataje View Post
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
henryzz is offline   Reply With Quote
Old 2009-01-05, 21:06   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

71348 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
bsquared is offline   Reply With Quote
Old 2009-01-05, 22:46   #11
mataje
 
mataje's Avatar
 
Jan 2009
Bilbao, Spain

283 Posts
Default

Quote:
Originally Posted by henryzz View Post
brilliant could you attach them in a zip here
Done.
Attached Files
File Type: zip Partition factors.zip (14.8 KB, 135 views)
mataje is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 10:20.


Thu Oct 6 10:20:04 UTC 2022 up 49 days, 7:48, 0 users, load averages: 1.06, 0.88, 0.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔