Discrete logarithm algorithm for modulus power of 2 For those of you that don't know, the modular/discrete logarithm problem:

Calculate b given the others: $a^b≡c$ mod d

I am aware that there is no general algorithm for the discrete logarithm, making it intractable. ($O(n^2)$ and worse for n digits is generally considered intractable, though exponential is for sure)

Even though it isn't standard, for simplicity I'll label time complexities here with the first letter:


$M(n)$ for multiplication
$D(n)$ for division
$E(n)$ for exponentiation


I have two conditions to work with:


d is a power of 2, so $d=2^n$ for some known n (this is convenient because modulo, which is $D(n)$, can be replaced by bitwise AND, which is $O(n)$)
a and c are odd, if not primes, which they probably will be (this could be inferred, since a has to be odd to generate all other odd values, of which c is one)


Naive brute force search would then be $O(2^nE(n))$. The best any algorithm (that I've heard of) does is subexponential - still not polynomial, which is what I'm aiming for.

I have algorithms for some of the other (non-trivial) ones, namely:

(Modular) Division


$D(n)=O(n^2)$ or so
Tested with 65536-bit numbers (Python, took a few seconds)


(Modular) Exponentiation


$E(n)=O(M(n)n)$, in my case, $M(n)=O(n^2)$ so $E(n)=O(n^3)$
Tested with 16384-bit numbers (Python, took a few seconds)


Discrete logarithm has me stumped. Since modulus power of 2 allows usage of various bit twiddling hacks and other shortcuts that normally would never work, I think it can be done in polynomial time for this case. No idea how though.
Suppose multiplication of two $n$-bit integers can be done in $\mathrm M(n)$ operations.

Here's an $\mathcal O(n^2\cdot\mathrm M(n))$ algorithm for discrete logarithms modulo $2^n$, which is basically the Pohlig-Hellman algorithm adapted to this specific problem. (With naïve multiplication, the runtime therefore is in $\mathcal O(n^4)$.)

First, observe that the order of the group $(\mathbb Z/2^n)^\ast$ is $2^{n-1}$: An integer in $\{0,\dots,2^n-1\}$ is invertible modulo $2^n$ if and only if it is odd. However, that group is not cyclic; in fact, its exponent is $2^{n-2}$.
So, set $k:=n-2$ and suppose $a$ has order $2^k$ modulo $2^n$. This is the maximal order one can achieve modulo $2^n$; in particular, there are no "primitive roots" modulo $2^n$ for $n\geq3$. This also implies that $b$ can only be uniquely determined modulo $2^k$.

The algorithm essentially works by repeatedly "shifting out" the higher-valued bits in the exponent until there is only one unknown bit left, and then brute-forcing that bit. "Shifting out" bits can be done by raising $c$ to powers of two:
Suppose the binary expansion of $b$ is $b=\sum_{i=0}^{k-1}2^ib_i$. Then, since $a^{2^l}\equiv0\pmod{2^n}$ for all $l\geq k$,
$$
  c^{2^i}
  = (a^b)^{2^i}
  = a^{2^ib}
  = a^{\sum_{j=0}^{k-1}2^{i+j}b_j}
  \equiv a^{\sum_{j=0}^{k-1-i}2^{i+j}b_j}
  \pmod{2^n}
  \text,
$$
which only depends on the lower $k-i$ bits of $b$.

In particular, we can start out with $i=k-1$, which will give
$$
  c^{2^{k-1}} \equiv a^{2^{k-1}b_0}\pmod{2^n}\text,
$$
and we can easily determine $b_0$ from this by trying both values $0$ and $1$ and checking which one satisfies the congruence. (Since we know it must be either of them, plugging in only $0$ or $1$ and seeing if it matches is also sufficient.)

Subsequently using $i=k-2$ yields
$$
  c^{2^{k-2}} \equiv a^{2^{k-2}b_0+2^{k-1}b_1}\pmod{2^n}\text,
$$
and since we already know $b_0$, we can compute $b_1$ by trying both (or only one of the) possible values.

Repeating this process will obtain all bits of $b$.



As for the runtime: To determine a single bit, we need to compute $c^{2^i}\bmod2^n$ and $a^{\sum_{j=0}^{k-1-i}2^{i+j}b_j}\bmod2^n$. Using fast exponentiation, powers modulo $2^n$ can be computed in $\mathcal O(n\cdot\mathrm M(n))$ operations, hence as we need to figure out $k\in\mathcal O(n)$ bits, the total runtime is in $\mathcal O(n^2\cdot\mathrm M(n))$.

In practice, one can save a few operations by computing all the values $c^{2^i}\bmod n$ and $a^{2^i}\bmod n$ in advance using repeated squaring. However, this does not improve the asymptotic complexity, as one still needs $\mathcal O(n)$ multiplications per bit of $b$ to combine the cached values of $a^{2^i}\bmod n$ according to the concrete known bits of $b$.