How can I find the exponent of a power of two from its remainder modulo a power of three?

Question

Suppose that ${2^m}\equiv k\pmod {3^n}$ and that I know $n$ and $k$. Is there a way to find the lowest (or indeed any) value for $m$ other than by enumerating the possibilities? Note: I'm aware that it's an intractable problem in the general case, but is there a known solution for this specific case? I'm only interested in powers of 2 and 3.

Answer 1

You are looking for the discrete logarithm function. You can read about it here. The are no efficient ways to calculate a discrete log, though it is possible if you don't have computational complexity concerns.

Answer 2

As I surmised, the unusual nature of the numbers 2 & 3 mean that there is a reasonably easy solution to this. For convenience, I define the discrete log function $\mathrm{Dlog}_a^b(n)$ as the lowest exponent $j$ such that $a^j\equiv n\pmod b$

We know $n$ and $k$, and we want to find $\mathrm{Dlog}_2^{3^k}(n)$. We can find this by successively calculating $\mathrm{Dlog}_2^{3^{k-1}}(n)$.

For all $k\ge 1$ and $n \neq 0$ (mod 3) the rule is:

When $k=1$, $$\mathrm{Dlog}_2^{3^k}(n) = n\pmod {3^k} - 1$$ In other words, $\mathrm{Dlog}_2^{3} \text{ of } 1, 2, 4, 5, 7 ... = 0, 1, 0, 1, 0 ...$

When $k\gt1$, $\mathrm{Dlog}_2^{3^k}(n) = (n^2-n*2^{\mathrm{Dlog}_2^{3^{k-1}}(n)})\pmod {3^k} * \frac23 +\mathrm{Dlog}_2^{3^{k-1}}(n)$.

For instance: to calculate $\mathrm{Dlog}_2^{27}(17)$ we calculate $$\mathrm{Dlog}_2^{3}(17)= 17\pmod 3 -1\\= 1$$ We can then calculate $$\mathrm{Dlog}_2^{9}(17) = (17^2-17*2^1)\pmod 9 * \frac23+1 \\= 255\pmod 9 * \frac23+1 \\=3* \frac23+1 \\= 3$$Finally, we can calculate$$\mathrm{Dlog}_2^{27}(17) = (17^2-17*2^3)\pmod{27} * \frac23+3 \\= 153\pmod {27} * \frac23+3 \\= 18* \frac23+3 \\=15$$In other words, $2^{15}\equiv 17 \pmod {27}$.