20160125, 23:24  #1 
Dec 2015
14_{16} Posts 
Distribution of weak numbers
Since this is going to be a more theoretical post, only indirectly connected to factoring, I'm not sure if this is the correct forum to post in. Please move this topic if there is a better forum for such discussions.
For the purposes of this discussion, I would like to define a Bweak number (where B is an integer)as any number of the form p^{k}*s, where p is a prime, and s is Bsmooth (a number not of this form is Bstrong). Such numbers are weak because they can be factored by a modern factoring utility using only pretesting algorithms (trial division, Pollard's rho, P1/P+1, ECM and prime power testing), without resorting to QS or NFS. In particular, 10^{40}smooth numbers are fairly tractable using a modern consumer PC, regardless of their size. In the recent TeslaCrypt key factorization campaign, many keys turned out to be of this form, prompting my inquiry. My question is: What is the distribution of Bweak numbers with respect of B? Also, is there a way to efficiently generate Bstrong numbers that's faster than generating semiprimes suitable for RSA moduli? 
20160125, 23:37  #2 
Tribal Bullet
Oct 2004
3·1,181 Posts 
Most of the time a theoretical analysis of the density of composites ignores the existence of powers; there are just so few powers compared to the nonpowers that they become very unlikely to appear at random.
The wiki page on smooth numbers is a good starting point for the analytic number theory that quantifies the probability that a random number is Bsmooth. The probability can be modified to account for one or two large factors that are bigger than B but all other factors less than B, and this has application for all the factorization methods. 
20160510, 04:54  #3 
May 2016
1 Posts 
Can we have a look of the Teslacrypt codebase? How can we test for this Bweak property?

20160511, 02:12  #4 
Romulan Interpreter
Jun 2011
Thailand
2^{4}·13·47 Posts 

20160511, 02:24  #5 
"Curtis"
Feb 2005
Riverside, CA
2^{7}·3·13 Posts 
If you want to test a particular number for Bweakness, you could try running ECM.

20160513, 15:10  #6 
Dec 2015
2^{2}×5 Posts 
A small error correction for the 1st post:
"In particular, 10^{40}smooth numbers are fairly tractable using a modern consumer PC, regardless of their size"  that was meant to read 10^{40}weak. Last fiddled with by Googulator on 20160513 at 15:10 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Goldbach's weak conjecture  MattcAnderson  MattcAnderson  19  20170321 18:17 
openssl weak keys  Unregistered  Information & Answers  1  20111007 22:14 
A (very) weak factoring method.  3.14159  Miscellaneous Math  29  20100531 23:21 
Distribution of Smooth Numbers  flouran  Math  12  20091225 16:41 