mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2016-01-25, 23:24   #1
Googulator
 
Dec 2015

2010 Posts
Question 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 pk*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, 1040-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?
Googulator is offline   Reply With Quote
Old 2016-01-25, 23:37   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

348910 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2016-05-10, 04:54   #3
odolo
 
May 2016

1 Posts
Default

Can we have a look of the Teslacrypt codebase? How can we test for this B-weak property?
odolo is offline   Reply With Quote
Old 2016-05-11, 02:12   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×23×97 Posts
Default

Quote:
Originally Posted by odolo View Post
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)
LaurV is offline   Reply With Quote
Old 2016-05-11, 02:24   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

24×32×31 Posts
Default

If you want to test a particular number for B-weakness, you could try running ECM.
VBCurtis is offline   Reply With Quote
Old 2016-05-13, 15:10   #6
Googulator
 
Dec 2015

22·5 Posts
Default

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

Last fiddled with by Googulator on 2016-05-13 at 15:10
Googulator is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Goldbach's weak conjecture MattcAnderson MattcAnderson 17 2017-03-21 18:17
Goldbach's weak conjecture MattcAnderson MattcAnderson 1 2017-03-18 23:32
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

All times are UTC. The time now is 19:04.

Mon Nov 23 19:04:09 UTC 2020 up 74 days, 16:15, 2 users, load averages: 3.00, 2.79, 2.68

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