HesapHanem

Quadratic Sieve Smoothness Calculator

Enter an integer and a smoothness bound B to test B-smoothness.

Result

5,460 is 10-smooth: no
2^2 x 3 x 5 x 7 x 13 (>B)
13

How it is calculated

The tool rounds n and B to whole numbers (both must be at least 2, and neither may exceed 9,007,199,254,740,992 = 253) and factors n completely: it divides out 2, then 3, 5, 7 and so on, removing each divisor as often as it fits, and uses a primality test on what is left so that large prime remainders are recognised quickly. The factorization is written like 2^3 x 3^2 x 5, and each prime factor above B is marked "(>B)". n is B-smooth when its largest prime factor is at most B, and that largest prime factor is shown separately. B does not limit the factoring, it only decides the yes or no. If n is a product of two or more primes that are all above roughly six million, the search is too long and no result is shown.

Worked example

Test n = 5460 with bound B = 10. Divide out 2 twice (5460 → 1365), 3 once (→ 455), 5 once (→ 91) and 7 once (→ 13). The remaining 13 is prime and larger than 10. The tool shows 5,460 is 10-smooth: no, with factorization 2^2 x 3 x 5 x 7 x 13 (>B) and largest prime factor 13. With B = 13 the same n gives "5,460 is 13-smooth: yes", because every prime factor is at most 13.

Try this example →

Common mistakes

  • Confusing B-smooth with having few factors. 5460 has five different prime factors and is 13-smooth, but not 10-smooth, because 13 is above the bound.
  • Setting B too low for the test you want. 360 = 2^3 x 3^2 x 5 passes with B = 5 but fails with B = 3 because of the factor 5.
  • Reading "(>B)" as a sign the number is composite. It marks any prime above the bound; for a prime n such as 97 with B = 50 the answer is simply 97 (>B).
  • Entering a decimal. 2.6 is rounded to 3 and tested as 3, not rejected.
  • Expecting every large number to work. If n is a product of two primes both above about six million, the tool gives no result instead of factoring it, which is exactly why such numbers are hard to attack.

About this calculator

The quadratic sieve smoothness calculator factors an integer n completely (trial division, with a primality test on whatever remains), reports whether n is B-smooth for a chosen smoothness bound B (meaning all of its prime factors are ≤ B), and returns the full prime factorization, marking each prime above B, along with the largest prime factor. If any prime factor is above B, n is not B-smooth.

Smoothness testing is the core screening step inside integer-factorization algorithms like the quadratic sieve and the general number field sieve, which don't try to factor a huge composite n directly — instead they search for many numbers related to n that happen to be B-smooth, then combine those relations with linear algebra to extract a factor. Cryptographers, number theory students, and researchers studying RSA-key factorization difficulty use this calculator to check smoothness on individual candidates and understand why a well-chosen key size keeps factoring computationally infeasible.

Was this helpful?

You can pick up to 3 reactions.

Comments (1)

  • Editorial team

    The tool factors n completely and calls it smooth when its largest prime factor does not exceed the bound B, so 5040 is 7-smooth (2^4 x 3^2 x 5 x 7). The limit is about 9 x 10^15, and a number with two very large prime factors can be too slow to split here and return nothing. Which bound B are you testing against?

Popular calculators

Loan Calculator

Monthly payment, total interest and full amortization schedule.

Percentage Calculator

Percent change, percent of, and ratio calculations.

Discount Calculator

Calculate final price, savings, and discount amount.

BMI Calculator

Body mass index from height and weight (metric or imperial).

Age Calculator

Compute your exact age in years, months and days from a birth date.

Compound Interest Calculator

Calculate the final amount and interest earned with compounding.

All Calculators