20160104, 18:29  #89 
I moo ablest echo power!
May 2013
1,801 Posts 
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 20160104 at 18:30 
20160104, 19:21  #90  
If I May
"Chris Halsall"
Sep 2002
Barbados
10591_{10} Posts 
Quote:
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 offline regularly. Trust no one. 

20160104, 19:31  #91 
I moo ablest echo power!
May 2013
1,801 Posts 
Munoz, your first number is fully factored. Last fiddled with by wombatman on 20160104 at 19:45 
20160105, 13:33  #92 
I moo ablest echo power!
May 2013
1,801 Posts 
Munoz, second one is factored as well: http://factordb.com/index.php?id=1100000000812695855

20160106, 01:33  #93  
Aug 2015
2×3^{3} Posts 
Quote:


20160106, 03:42  #94 
I moo ablest echo power!
May 2013
1,801 Posts 
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.

20160106, 04:49  #95 
Aug 2015
66_{8} Posts 
Oh by input I meant prime factor

20160106, 05:20  #96 
"Curtis"
Feb 2005
Riverside, CA
12407_{8} Posts 
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 primefactor size as well as composite size but the size of the factor dominates the expected runtime. Last fiddled with by VBCurtis on 20160106 at 05:20 
20160106, 05:39  #97 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
16065_{8} Posts 
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. 
20160106, 07:42  #98 
Romulan Interpreter
"name field"
Jun 2011
Thailand
17·19·31 Posts 
How about "a graph worth a thousand words"?
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 subexponential 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 P1 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 20160106 at 09:03 Reason: added a time scale to the graphic, for clarity; s/overload/overhead/g 
20160106, 08:05  #99 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
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 constantsize overhead becomes insignificant).

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Using msieve with c  burrobert  Msieve  9  20121026 22:46 
Yes: Tales from Typographic Oceans  xilman  Lounge  79  20120526 23:53 
msieve help  em99010pepe  Msieve  23  20090927 16:13 
95% sure I have a virus, please help  jasong  Hardware  8  20061119 22:57 
virus hardware damage?  TTn  Hardware  18  20061104 09:41 