Binary Exponentiation by Factoring

Compute a · xʸ (mod 2ᵈ) for odd x and d ≥ 3 using O(d) additions / bit ops and one multiply by y — not the usual O(log y) modular multiplies.

This lesson follows CP-Algorithms — Factoring Exponentiation.

Why it works

The multiplicative group modulo 2ᵈ is special. Any x ≡ 1 (mod 4) can be written

x ≡ b^{L(x)}  (mod 2ᵈ)

for a fixed generator-like base b ≡ 5 (mod 8). Then

a · xʸ ≡ a · b^{y · L(x)}  (mod 2ᵈ)

If x ≡ 3 (mod 4), reduce to the ≡ 1 (mod 4) case by x ↦ −x and a ↦ (−1)ʸ · a.

We work with 4 L(x) (taken mod 2ᵈ) instead of L(x) mod 2ᵈ⁻² — that scaling makes bit-decomposition of the discrete log clean.

32-bit API

Function	Meaning
mbin_log_32(r, x)	r + 4 L(x) (mod 2³²)
mbin_exp_32(r, x)	r · b^{x/4} (mod 2³²)
mbin_power_odd_32(a, x, y)	a · xʸ (mod 2³²) for odd x

uint32_t mbin_power_odd_32(uint32_t rem, uint32_t base, uint32_t exp) {
    if (base & 2) {
        /* base ≡ 3 (mod 4): treat as negative */
        base = -base;
        if (exp & 1) {
            rem = -rem;
        }
    }
    return mbin_exp_32(rem, mbin_log_32(0, base) * exp);
}

Check: setup

Quiz

Factoring exponentiation setup

1 / 4

The method targets which modulus?

Pick an answer to see if you are right.

Computing 4 L(x) from x

Odd x ≡ 1 (mod 4) factors (mod 2ᵈ) as a product of terms 2^{aᵢ} + 1 with 1 < a₁ < … < aₖ < d. Discrete logs add:

4 L(x) ≡ Σ 4 L(2^{aᵢ} + 1)  (mod 2ᵈ)

Precompute table[n] = 4 L(2ⁿ + 1) for 1 < n < d. For 32-bit:

const uint32_t mbin_log_32_table[32] = {
    0x00000000, 0x00000000, 0xd3cfd984, 0x9ee62e18,
    0xe83d9070, 0xb59e81e0, 0xa17407c0, 0xce601f80,
    0xf4807f00, 0xe701fe00, 0xbe07fc00, 0xfc1ff800,
    0xf87ff000, 0xf1ffe000, 0xe7ffc000, 0xdfff8000,
    0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
    0xfff00000, 0xffe00000, 0xffc00000, 0xff800000,
    0xff000000, 0xfe000000, 0xfc000000, 0xf8000000,
    0xf0000000, 0xe0000000, 0xc0000000, 0x80000000,
};

In code we do not factor x directly. We multiply by 2ⁿ+1 until x ≡ 1, which builds the factorization of x⁻¹. Since 4 L(x) = −4 L(x⁻¹), we subtract table entries:

uint32_t mbin_log_32(uint32_t r, uint32_t x) {
    uint8_t n;
    for (n = 2; n < 32; n++) {
        if (x & (1 << n)) {
            x = x + (x << n);           // *= (2^n + 1)
            r -= mbin_log_32_table[n];
        }
    }
    return r;
}

x + (x << n) clears bit n and leaves bits < n unchanged (x odd).

Computing x from 4 L(x) (mbin_exp)

Orders of the factors 2ⁿ+1 divide powers of two. Working with 4 L makes the discrete log uniquely bit-decomposable: if bit n of the current log is set, multiply the accumulator by 2ⁿ+1 and subtract table[n].

uint32_t mbin_exp_32(uint32_t r, uint32_t x) {
    uint8_t n;
    for (n = 2; n < 32; n++) {
        if (x & (1 << n)) {
            r = r + (r << n);
            x -= mbin_log_32_table[n];
        }
    }
    return r;
}

🧪 Verify a·xʸ mod 2³² against builtin multiply-pow

Interactive: log loop shape

Toy 8-bit walk of the same “if bit n set, x += x≪n” idea (table values are illustrative).

Further optimizations

For 2n ≥ d, 4 L(2ⁿ+1) = 2ⁿ. So you can loop only to d/2 and finish with bit masks:

uint32_t mbin_log_32(uint32_t r, uint32_t x) {
    for (uint8_t n = 2; n != 16; n++) {
        if (x & (1 << n)) {
            x = x + (x << n);
            r -= mbin_log_32_table[n];
        }
    }
    r -= (x & 0xFFFF0000);
    return r;
}

uint32_t mbin_exp_32(uint32_t r, uint32_t x) {
    for (uint8_t n = 2; n != 16; n++) {
        if (x & (1 << n)) {
            r = r + (r << n);
            x -= mbin_log_32_table[n];
        }
    }
    r *= 1 - (x & 0xFFFF0000);
    return r;
}

Building the log table

table[n] = 4 L(2ⁿ+1) is a discrete log base g = 5 of y = 2ⁿ+1 mod 2ᵈ. Adapt Pohlig–Hellman to power-of-two moduli: repeatedly square to read the lowest unknown bit of the exponent, peel it off with g^{-x₀}, and continue until all bits are known.

Check: log / exp loops

Quiz

Log and exp loops

1 / 4

x = x + (x << n) implements…

Pick an answer to see if you are right.

Practice drills

Activity: Detect ≡ 3 mod 4

Odd x. Print YES if x ≡ 3 (mod 4) (needs the sign flip in mbin_power_odd), else NO.

References

• M30, Hans Petter Selasky, 2009 (as cited on CP-Algorithms)

Cheat sheet

Piece	Role
Goal	a xʸ mod 2ᵈ, odd x
Encoding	x = b^{L(x)}, work with 4 L
log	clear bits via *(2ⁿ+1), subtract table
exp	set bits via *(2ⁿ+1), subtract table from log
power	exp(rem, log(base) * y) after sign fix
Fast path	loop to d/2, mask the high half