Modular Binomial Equation Attack

Updated 19 Sep 2026

•
What it is
- •
  A technique for recovering the two prime factors $p, q$ of $N = pq$ when you're given two ciphertexts that are each a linear combination of $p$ and $q$ raised to a public exponent: $c_1 = (a_1 p + b_1 q)^{e_1} \bmod N$ , $c_2 = (a_2 p + b_2 q)^{e_2} \bmod N$ .
•
When to apply
- •
  $N = p \cdot q$ is given, and both ciphertexts are visibly "binomial" — small known integer coefficients multiplying $p$ and $q$ before exponentiation. That coefficient structure is the tell.
•
Math
- •
  Modulo $q$ , the $b_i q$ term vanishes, leaving $c_1^{e_2} \equiv (a_1 p)^{e_1 e_2}$ and $c_2^{e_1} \equiv (a_2 p)^{e_1 e_2} \pmod q$ . Scaling each by the modular inverse of its $a_i^{e_1 e_2}$ term makes both sides equal to $p^{e_1 e_2} \bmod q$ , so their difference is $\equiv 0 \pmod q$ — meaning $q$ divides it. Taking $\gcd$ with $N$ recovers $q$ :
- •
  $q = \gcd\!\big(a_2^{-e_1 e_2} c_2^{e_1} - a_1^{-e_1 e_2} c_1^{e_2},\; N\big)$
•
Worked example
- •
  Take $p=7$ , $q=11$ , $N=77$ , $c_1=(2p+3q)^3\bmod N=27$ , and $c_2=(5p+7q)^5\bmod N=21$ . Let $E=15$ .
- •
  Compute $\Delta=5^E c_1^5-2^E c_2^3\bmod N=22$ . Then $\gcd(22,77)=11=q$ , and $p=N/q=7$ . A toy instance can occasionally make $\Delta$ divisible by both primes; reject gcd values $1$ and $N$ .

Python

expr = (pow(a2, -e1 * e2, N) * pow(c2, e1, N) - pow(a1, -e1 * e2, N) * pow(c1, e2, N)) % N
q = math.gcd(expr, N)
p = N // q

expr = mod(power_mod(a2, -e1*e2, N) * power_mod(c2, e1, N) - power_mod(a1, -e1*e2, N) * power_mod(c1, e2, N), N)
q = gcd(Integer(expr), N)