Quadratic Sieve Smoothness Calculator

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

How it is calculated

n and B must be whole numbers (a decimal such as 5460.5 for n or 10.6 for B gives no result); both must be at least 2, and neither may exceed 9,007,199,254,740,992 = 253. The tool 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 recognized 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 n such as 2.6, or a decimal bound such as B = 10.6: the tool gives no result for either, so enter whole numbers.
  • 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.

Sources

  • A Tale of Two Sieves — Carl Pomerance, Notices of the American Mathematical Society 43(12), 1996

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.

Note from the editors

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. Take 1001, which is 7 x 11 x 13: with B = 12 the tool says no, with B = 13 yes, so the bound alone changes the verdict. Which bound B are you testing against?

Comments

  • Be the first to comment.

Popular calculators

All Calculators