Discrete Log Reduction via Chosen Composite Modulus n=q² (Paillier's Trick)

Updated 19 Sep 2026

•
What it is
- •
  If a protocol lets an attacker choose the modulus a discrete-log-based scheme operates over — subject only to a loose compatibility check like " $g^q \equiv 1 \pmod n$ " for a fixed public $q$ — picking $n = q^2$ and $g = q+1$ turns the discrete logarithm problem into trivial division. This is the exact algebraic trick behind the Paillier cryptosystem's decryption: by the binomial theorem, $(1+q)^x = \sum_k \binom{x}{k} q^k \equiv 1 + xq \pmod{q^2}$ , since every term with $k\ge 2$ contains a factor of $q^2$ and vanishes. Computing $h = g^x \bmod n$ with these chosen parameters directly and losslessly encodes $x$ in $h$ , recoverable by simple integer division — no discrete-log algorithm needed at all.
•
When to apply
- •
  A protocol asks you to supply your own group parameters (a modulus $n$ , a generator $g$ ) subject only to a simple checkable relation, rather than fixing them to a hard, well-vetted group in advance — a clean signal that the "hard" discrete log problem might be escapable by choosing a deliberately weak, structured group.
•
Math
- •
  $(1+q)^x \bmod q^2 = 1 + xq \bmod q^2$ exactly, so $x = \dfrac{h - 1}{q}$ .
•
Worked example
- •
  Let $q=7$ , $n=49$ , $g=8=1+q$ , and $x=4$ . Then $g^x\bmod n=29=1+4q$ , so $(29-1)/7=4$ . In general this recovers $x\bmod q$ ; recovering an unrestricted exponent requires an external bound or more information.

Python

n = q**2
g = q + 1
# server computes h = pow(g, x, n) using these chosen parameters
x = (h - 1) // q