mersenneforum.org Distribution of weak numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2016-01-25, 23:24 #1 Googulator   Dec 2015 248 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 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?
 2016-01-25, 23:37 #2 jasonp Tribal Bullet     Oct 2004 354310 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 12 Posts Can we have a look of the Teslacrypt codebase? How can we test for this B-weak property?
2016-05-11, 02:12   #4
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

986910 Posts

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)

 2016-05-11, 02:24 #5 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2·2,579 Posts If you want to test a particular number for B-weakness, you could try running ECM.
 2016-05-13, 15:10 #6 Googulator   Dec 2015 22·5 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 19 2017-03-21 18:17 Unregistered Information & Answers 1 2011-10-07 22:14 3.14159 Miscellaneous Math 29 2010-05-31 23:21 flouran Math 12 2009-12-25 16:41

All times are UTC. The time now is 20:47.

Sat Jan 22 20:47:56 UTC 2022 up 183 days, 15:16, 0 users, load averages: 1.99, 1.75, 1.82

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.

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