Factoring Products of Mersenne-Form Numbers (2^a-1)(2^b-1)

Updated 13 Sep 2026

•
What it is
- •
  If an RSA-style modulus is built from two numbers of the specific form $2^a-1$ and $2^b-1$ (regardless of whether they're genuinely prime — the vulnerability is purely structural), the modulus can be factored almost immediately from the bit pattern of $N-1$ alone (in the common case $a \ne b$ ), without any general-purpose factoring algorithm. Assuming $a<b$ : $N-1$ factors as $2^a$ times an odd number, so counting how many times $N-1$ divides evenly by 2 directly reveals $a$ (the smaller exponent), from which $p=2^a-1$ falls out immediately and $q=N/p$ .
•
When to apply
- •
  Prime-generation code explicitly builds numbers as (1 << k) - 1 for some secret exponent $k$ (a "Mersenne-form" number) — a huge red flag regardless of whether the code bothers to verify actual primality of the result.
•
Math
- •
  For $a<b$ : $N-1 = 2^a(2^{b-a}-1)\cdot(\text{odd part})$ — the exact count of trailing zero bits in $N-1$ (its 2-adic valuation) equals $a$ . (Special case: if $a=b$ , i.e. $p=q$ , $N$ is a perfect square instead — see RSA with p = q (Repeated Prime Factor).)
•
Worked example
- •
  $p = 2^{89}-1$ , $q=2^{127}-1$ (both real historical Mersenne-prime exponents): counting trailing zero bits of $N-1$ gave exactly 89 — recovering $p=2^{89}-1$ and $q=N/p$ exactly, matching the true factorization.

Python

z = N - 1
a = 0
while z % 2 == 0:
        z //= 2
        a += 1
p = (1 << a) - 1
q = N // p

•
SageMath
- •
  Not particularly relevant — this is a direct bit-counting loop, equally minimal in either language. (An alternative, more general approach — computing gcd(N, 2^k mod N - 1) for a range of candidate k — also works and generalizes better if the exact structural form isn't fully known in advance.)
•
Cards
- •
  Why does counting trailing zero bits of N-1 reveal the smaller exponent a?
  - •
    N-1 = 2^a · (odd number) when p=2^a-1, q=2^b-1 with a<b, so the 2-adic valuation of N-1 is exactly a.
- •
  What's the giveaway in source code that this technique applies?
  - •
    Prime generation explicitly constructs candidates as (1 << k) - 1 for a secret exponent k — a "Mersenne-form" number — rather than a standard random-prime generator.