THE GARDEN

Fermat's Factorization Method (Close Primes)

Updated 19 Sep 2026

• •

  What it is

  • •

    A factorization technique (dating to Fermat, centuries before RSA) that's extremely fast whenever a composite $N=pq$ has two factors close to each other in size. Since $N = a^2 - b^2 = (a-b)(a+b)$ for $a=\frac{p+q}{2}, b=\frac{p-q}{2}$, starting from $a=\lceil\sqrt N\rceil$ and incrementing $a$ by 1 each step while checking whether $a^2-N$ is a perfect square finds $b$ (and hence $p,q$) in roughly $|p-q|/2$ steps — trivially fast if $p$ and $q$ are close, hopelessly slow if they aren't.

• •

  When to apply

  • •

    RSA key generation that derives $p$ and $q$ from a shared starting value (or otherwise biases them toward being close together) — a strong tell is any prime-generation routine that starts both primes from the same random seed and nudges them upward by comparatively small increments until each is prime.

• •

  Math

  • •

    $N=(a-b)(a+b)$ where $a=\lceil\sqrt N\rceil + k$ for increasing $k=0,1,2,\dots$, testing whether $a^2-N$ is a perfect square at each step; once found, $p=a-b$, $q=a+b$.

• •

  Worked example

  • •

    $N=10403=101\cdot103$. Start at $a=\lceil\sqrt N\rceil=102$; $a^2-N=1$ is already a square, so $b=1$ and the factors are $a-b=101$ and $a+b=103$. Runtime grows with the gap between the factors.

• •

  Python

  • •

    from math import isqrt
    def fermat_factor(n):
            a = isqrt(n)
            if a*a < n:
                a += 1
            b2 = a*a - n
            while isqrt(b2)**2 != b2:
                a += 1
                b2 = a*a - n
            b = isqrt(b2)
            return a - b, a + b
    

• •

  SageMath

  • •

    is_square() and ceil(sqrt(n)) tidy the syntax, but the loop structure is identical to the Python version — this isn't a case where Sage changes the approach.

• •

  Related

  • •

    RSA (Textbook Construction)

• •

  Cards

  • •

    What structural weakness does Fermat's factorization method exploit?

    • •

      The two prime factors being close in size — the closer they are, the fewer iterations the search needs.

  • •

    What's the core algebraic identity behind the method?

    • •

      N = a² - b² = (a-b)(a+b), searching upward from a = ⌈√N⌉ for the first a where a²-N is a perfect square.

◌ Explore connections in Graph view