Distribution of weak numbers

Googulator · 2016-01-25, 23:24

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 B-weak number (where B is an integer)as any number of the form p^k*s, where p is a prime, and s is B-smooth (a number not of this form is B-strong). Such numbers are weak because they can be factored by a modern factoring utility using only pretesting algorithms (trial division, Pollard's rho, P-1/P+1, ECM and prime power testing), without resorting to QS or NFS. In particular, 10⁴⁰-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 B-weak numbers with respect of B? Also, is there a way to efficiently generate B-strong numbers that's faster than generating semiprimes suitable for RSA moduli?

jasonp · 2016-01-25, 23:37

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 non-powers 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 B-smooth. 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.

odolo · 2016-05-10, 04:54

Can we have a look of the Teslacrypt codebase? How can we test for this B-weak property?

LaurV · 2016-05-11, 02:12

Quote:

Originally Posted by odolo

Can we have a look of the Teslacrypt codebase? How can we test for this B-weak property?

Do you want to improve teslacrypt, or what?

(unclear)

VBCurtis · 2016-05-11, 02:24

If you want to test a particular number for B-weakness, you could try running ECM.

Googulator · 2016-05-13, 15:10

A small error correction for the 1st post:
"In particular, 10⁴⁰-smooth numbers are fairly tractable using a modern consumer PC, regardless of their size" - that was meant to read 10⁴⁰-weak.

2016-01-25, 23:24	#1
Googulator Dec 2015 20₁₀ 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 B-weak number (where B is an integer)as any number of the form p^ks, where p is a prime, and s is B-smooth (a number not of this form is B-strong*). Such numbers are weak because they can be factored by a modern factoring utility using only pretesting algorithms (trial division, Pollard's rho, P-1/P+1, ECM and prime power testing), without resorting to QS or NFS. In particular, 10⁴⁰-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 B-weak numbers with respect of B? Also, is there a way to efficiently generate B-strong numbers that's faster than generating semiprimes suitable for RSA moduli?

2016-05-13, 15:10	#6
Googulator Dec 2015 2²×5 Posts	A small error correction for the 1st post: "In particular, 10⁴⁰-smooth numbers are fairly tractable using a modern consumer PC, regardless of their size" - that was meant to read 10⁴⁰-weak. Last fiddled with by Googulator on 2016-05-13 at 15:10

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Goldbach's weak conjecture	MattcAnderson	MattcAnderson	19	2017-03-21 18:17
openssl weak keys	Unregistered	Information & Answers	1	2011-10-07 22:14
A (very) weak factoring method.	3.14159	Miscellaneous Math	29	2010-05-31 23:21
Distribution of Smooth Numbers	flouran	Math	12	2009-12-25 16:41

2016-01-25, 23:37	#2
jasonp Tribal Bullet Oct 2004 5·709 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 non-powers 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 B-smooth. 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.

2016-05-10, 04:54	#3
odolo May 2016 1 Posts	Can we have a look of the Teslacrypt codebase? How can we test for this B-weak property?

2016-05-11, 02:24	#5
VBCurtis "Curtis" Feb 2005 Riverside, CA 1010010011111₂ Posts	If you want to test a particular number for B-weakness, you could try running ECM.