Roots of Unity mod N (Non-Trivial Roots Reveal Factors)

Updated 13 Sep 2026

• •

  What it is

  • •

    An $n$-th root of unity modulo $N$ is any value $x$ satisfying $x^n \equiv 1 \pmod N$. Modulo a prime, the only square roots of unity are $\pm 1$ — a direct consequence of $x^2-1=(x-1)(x+1)$ having at most 2 roots in a field. Modulo a composite $N=pq$, though, the Chinese Remainder Theorem guarantees four square roots of unity exist (one combination of $\pm1 \bmod p$ and $\pm1 \bmod q$ each) — meaning a value $x \ne \pm1 \pmod N$ with $x^2\equiv1\pmod N$ can exist, and finding one is exactly as good as factoring $N$: $\gcd(x-1,N)$ splits off a genuine, non-trivial factor immediately. This single fact is the shared mechanism behind Miller-Rabin's ability to detect composite numbers, the classic "factor N given a known (e,d) pair" algorithm, and RSA's "unconcealed message" fixed-point weakness — all three reduce to "find a non-trivial square root of unity mod N," just arriving at the search differently.

• •

  When to apply

  • •

    Any time you have (or can construct) a value with known order dividing some power of 2 modulo an unfactored composite $N$ — repeatedly squaring down from that value and checking $\gcd(x-1,N)$ at each step is the standard way to convert that knowledge directly into a factorization.

• •

  Symbols and assumptions

  • •

    $N=pq$ with distinct odd primes. A square root of unity is an $x$ satisfying $x^2\equiv1\pmod N$. The roots $x=\pm1$ are called trivial here.

• •

  Math — step by step

  • •
    1. Rewrite $x^2-1=(x-1)(x+1)$. If $x^2\equiv1\pmod N$, then each prime factor of $N$ divides one of those factors.
  • •
    2. A nontrivial root has opposite signs in the two CRT components, for example $x\equiv1\pmod p$ and $x\equiv-1\pmod q$. Consequently $\gcd(x-1,N)$ reveals one prime.
  • •
    3. When the signs agree, the gcd is 1 or $N$ and gives no factor. Verify $1<d<N$ before using $d$ as a factor.
• •

  Worked example

  • •

    Let $N=77=7\cdot11$ and $x=34$. Then $34\equiv-1\pmod7$ and $34\equiv1\pmod{11}$.

  • •

    Check $34^2-1=1155=15\cdot77$. Now $\gcd(33,77)=11$ and $\gcd(35,77)=7$. The two gcds separate the factors.

• •

  Python

  • •

    from math import gcd
    x = starting_value  # known to have order dividing some power of 2, mod N
    for _ in range(30):
            x = pow(x, 2, N)
            g = gcd(x - 1, N)
            if 1 < g < N:
                p, q = g, N // g
                break
    

• •

  Related

  • •

    RSA Factorization from Known (N, e, d)

  • •

    RSA Fixed-Point Leakage (Unconcealed Messages) → Factorization

  • •

    RSA with Non-Coprime Exponent (e Shares a Factor with φ(N))

  • •

    Miller-Rabin Primality Test

• •

  Cards

  • •

    How many square roots of unity does a composite N=pq have, versus a prime modulus?

    • •

      Exactly 4, versus only 2 (±1) for a prime modulus — the extra two "non-trivial" roots only exist because N is composite.

  • •

    Why does finding a non-trivial square root of unity mod N immediately give you a factor?

    • •

      gcd(x-1, N) evaluates to exactly one of N's two prime factors, since x agrees with +1 modulo one factor and -1 modulo the other.

◌ Explore connections in Graph view