THE GARDEN

Smooth Numbers & Constructing Smooth Primes

Updated 13 Sep 2026

• •

  What it is

  • •

    A "smooth" number is one whose prime factorization consists entirely of small primes (below some chosen bound, called the smoothness bound). Smoothness matters throughout cryptanalysis because many hard-problem algorithms secretly become easy when a relevant number turns out to be smooth: Pohlig-Hellman needs a smooth group order, Pollard's p-1 factorization method needs one prime factor of a target to be $p-1$-smooth, index calculus / ECM factoring lean on smoothness too, and Arnault-style strong-pseudoprime construction needs several related primes built around smooth structure. Offensively, when an attacker gets to choose a modulus themselves (e.g. because a protocol accepts caller-supplied Diffie-Hellman parameters), they can deliberately construct one that's smooth — real, prime, and outwardly unremarkable, but secretly weak.

• •

  When to apply

  • •

    You control (or want to construct) a modulus for use in an attack that specifically needs a smooth group order — most commonly, setting up a target for Pohlig-Hellman, or (in a very different context) constructing smooth-adjacent primes to defeat a fixed-basis Miller-Rabin check.

• •

  Symbols and assumptions

  • •

    An integer is $B$-smooth if all its prime factors are at most $B$. For DLP, the important smooth integer is the group order, such as $p-1$, not the prime modulus $p$ itself.

• •

  Math — step by step

  • •
    1. Construct a candidate group order $v$ as a product of small primes and powers. Then test $p=v+1$ for primality.
  • •
    2. If $p$ is prime, $\mathbb F_p^\times$ has known smooth order $v$. The base may generate a smaller subgroup, so determine its actual order before solving a DLP.
  • •
    3. Not every $v+1$ is prime; vary the factor choices and retest. This constructs a prime with smooth $p-1$, not a large prime that itself has small prime factors.
• •

  Worked example

  • •

    Take $v=2^4\cdot3=48$. Then $p=49=7^2$ is composite, so reject it.

  • •

    Try $v=2^5\cdot3=96$. Now $p=97$ is prime, and $p-1=96$ has only prime factors 2 and 3.

  • •

    The full multiplicative group therefore has order 96; Pohlig-Hellman reduces its DLP to small-prime digit problems.

• •

  Python

  • •

    def build_smooth_prime(min_bits, small_primes):
            v, i = 1, 0
            while v.bit_length() < min_bits:
                v *= small_primes[i % len(small_primes)]
                i += 1
            p = v + 1
            while not is_prime(p):
                v *= small_primes[i % len(small_primes)]
                i += 1
                p = v + 1
            return p, v   # p is smooth-order-plus-one; v = p-1 is fully smooth
    

• •

  SageMath

  • •

    def build_smooth_prime(min_bits, small_primes):
            v = prod(small_primes)  # or build up incrementally as in the Python version
            while not is_prime(v + 1):
                v *= next_prime(small_primes[-1])
            return v + 1
    

• •

  Related

  • •

    Pohlig-Hellman Algorithm

  • •

    Integer Factorization via ECM - Sage's factor()

  • •

    Miller-Rabin Primality Test

• •

  Cards

  • •

    Why does an attacker who can choose their own modulus want it to be smooth?

    • •

      A smooth group order makes Pohlig-Hellman efficient against it, turning an otherwise-hard discrete log problem into a fast one, while the modulus itself can still look like an ordinary large prime.

  • •

    What's the basic construction strategy for building a smooth prime?

    • •

      Multiply together small primes until the product reaches the target bit-length, add 1, and test primality — retry with additional small factors if the result isn't prime.

◌ Explore connections in Graph view