mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2016-01-04, 18:29   #89
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

1,801 Posts
Default

Your first number will be here (not factored fully yet): http://factordb.com/index.php?id=1100000000812652970

Your second will be here: http://factordb.com/index.php?id=1100000000812695855

It didn't work because that last large number (starting with 322...) is not fully factored yet.

Try YAFU first on both of the unfactored numbers (see the factordb links in this post).

Last fiddled with by wombatman on 2016-01-04 at 18:30
wombatman is offline   Reply With Quote
Old 2016-01-04, 19:21   #90
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

7·17·89 Posts
Default

Quote:
Originally Posted by wombatman View Post
It didn't work because that last large number (starting with 322...) is not fully factored yet.
Just to put this out there...

This "ransomware" went easy on many.

The next time they'll get their code correct.

Don't click on links and download stuff. Never click "OK" when a program asks to escalate it's permissions.

Back up off-line regularly.

Trust no one.
chalsall is online now   Reply With Quote
Old 2016-01-04, 19:31   #91
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

1,801 Posts
Default



Munoz, your first number is fully factored.

Last fiddled with by wombatman on 2016-01-04 at 19:45
wombatman is offline   Reply With Quote
Old 2016-01-05, 13:33   #92
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

1,801 Posts
Default

Munoz, second one is factored as well: http://factordb.com/index.php?id=1100000000812695855
wombatman is offline   Reply With Quote
Old 2016-01-06, 01:33   #93
jux
 
jux's Avatar
 
Aug 2015

2·33 Posts
Default

Quote:
Originally Posted by wombatman View Post
Munoz, second one is factored as well: http://factordb.com/index.php?id=1100000000812695855
I was just a few hours late...I did get a useful benchmark though. My factorization took somewhat longer than I expected - maybe it was because the two inputs were relatively unequal in size?
jux is offline   Reply With Quote
Old 2016-01-06, 03:42   #94
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

1,801 Posts
Default

Probably so. For every 5 digit increase in terms of the size of the composite, the time to factor it roughly doubles, if I recall correctly.
wombatman is offline   Reply With Quote
Old 2016-01-06, 04:49   #95
jux
 
jux's Avatar
 
Aug 2015

5410 Posts
Default

Oh by input I meant prime factor
jux is offline   Reply With Quote
Old 2016-01-06, 05:20   #96
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

150716 Posts
Default

The input is the composite. The outputs are the primes. The time for the factorization to run (GNFS) is a function of input size, not output size. Even composites that break into 3 primes are not meaningfully longer jobs (though the sqrt step may take more iterations to recover all 3 factors). As The Wombat says, every 5 digits roughly doubles factorization effort for GNFS.

For an ECM run, the (expected) time to find a factor is a function of prime-factor size as well as composite size- but the size of the factor dominates the expected runtime.

Last fiddled with by VBCurtis on 2016-01-06 at 05:20
VBCurtis is offline   Reply With Quote
Old 2016-01-06, 05:39   #97
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

1C3516 Posts
Default

To summarize, some numbers are made up of entirely small factors, which can be found by ECM. If a number fails to be factored by ECM, then it's likely got "large" factors, and on average it's less time to switch to NFS, which while substantially longer than the ECM stage run by YAFU, it is roughly fixed duration (based on input composite size), unlike ECM, and is "guaranteed" to produce results, no matter the size of the factors, again unlike ECM.

So when factoring these teslacrypt key, the run time being "short" or "long" more or less boils down to if it was necessary to resort to NFS, i.e. if there is more than 1 large factor.

For the most recent key we are discussing, the small factors are found by simpler methods, then ECM was run on the resulting C147, which successfully knocked out the P20. Then there would be a C127 left, and after ECM tried and failed to find factors up to around ~39 digits, it gave up and ran NFS on the C127, resulting in the seemingly longer run time. The NFS of course split the C127 as P54*P74.
Dubslow is offline   Reply With Quote
Old 2016-01-06, 07:42   #98
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

1001310 Posts
Default

How about "a graph worth a thousand words"?
Click image for larger version

Name:	factoring_algs.PNG
Views:	217
Size:	76.4 KB
ID:	13677
This I put together right now, during the lunch break, maybe it is not exactly... exact, but it will give to the beginners an idea of what's going on. The trial factoring is faster at first, because it has no "overhead", you just try every prime in order, and see if your number splits in small primes. With every digit you add, you have to test many more primes, so if you don't find a small factor fast, then the time becomes too long, exponentially long, and you have to switch to a more efficient algorithm. There are some algorithms out there which will find a factor if the factor has some special form, or property, or if the composite is not too big (like QS for example), and if you are lucky and the factor has such property, you still can find the factor "almost efficiently" (i.e. in sub-exponential time). This "based on luck" condition is symbolized by the dotted lines on the graphic. These algorithms have some "overhead" that you have to do, before (and during) you find/look for/ the factor, that is why they are not suitable to look for very small factors (where TF is faster, as not many primes to be tested). Also, they may or may not find the factors, depending on their properties, and your luck. For example, Pollard rho may find the factors if they are "close together", or P-1 may find the factors if they are "smooth", or ECM may find the factor if some magic animal called "group order" of it is enough smooth, and you were enough lucky to start with the right "seed". But all these algorithms work "between some limits", and when you increase the limits, to extend the size or the properties set of the factors you are searching, then the working time also goes up very fast. At the end, you unlucky poor bastard who didn't find a factor, are left with NFS and you have to crunch at it for days, or sometimes weeks (where other algorithms would take months/years, and TF would take centuries).

Last fiddled with by Batalov on 2016-01-06 at 09:03 Reason: added a time scale to the graphic, for clarity; s/overload/overhead/g
LaurV is offline   Reply With Quote
Old 2016-01-06, 08:05   #99
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts
Default

I think you are looking for "overhead" rather than "overload"? In the sense of a minimum constant effort for any job, no matter how small (while for larger jobs the constant-size overhead becomes insignificant).
Dubslow 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
Yes: Tales from Typographic Oceans xilman Lounge 79 2012-05-26 23:53
msieve help em99010pepe Msieve 23 2009-09-27 16:13
95% sure I have a virus, please help jasong Hardware 8 2006-11-19 22:57
virus hardware damage? TTn Hardware 18 2006-11-04 09:41

All times are UTC. The time now is 00:15.


Tue Aug 16 00:15:17 UTC 2022 up 39 days, 19:02, 1 user, load averages: 1.72, 1.46, 1.36

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.

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