B-smooth number: all prime factors ≤ B. 720 = 2⁴·3²·5 is 5-smooth. 7-smooth numbers: 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21... Critical in modern factoring: quadratic sieve and GNFS collect smooth relations. The probability a random n-digit number is n^(1/u)-smooth is u^(-u).
How to Use
Enter n and B:
- B-smooth?: All factors ≤ B?
- Largest factor: The smoothness bound
- Factorization: Complete decomposition
Factoring Algorithms
The quadratic sieve and GNFS factor large numbers by finding B-smooth values of polynomials. Choosing optimal B is crucial: too small = few smooth values, too large = too many primes in the factor base. Optimal B ≈ exp(√(ln n · ln ln n)).
Counting Smooth Numbers
Ψ(x,y) = count of y-smooth numbers ≤ x. Dickman's function: Ψ(x,x^(1/u)) ≈ x·ρ(u). ρ(1)=1, ρ(u) decreases rapidly: ρ(2)≈0.31, ρ(3)≈0.049, ρ(5)≈0.00035.
Step-by-Step Instructions
- 1Enter number.
- 2Set smoothness B.
- 3Check smooth.
- 4View factors.
- 5Compare bounds.