Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

Question

I'm seeking an efficient algorithm for the problem:

Input: The positive integer $3^n$ (stored as bits) for some integer $n \geq 0$.

Output: The number $n$.

Question: Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

---

This is a theoretical question motivated by my answer to a math.SE question How to find a formula for this bijection?. In this question, the author wanted to find a bijection from $$\{2^n 3^m: n \geq 0 \text{ and } m \geq 0\}$$ and the natural numbers $\mathbb{N}=\{1,2,\ldots\}$. I proposed $$2^m 3^n \mapsto 2^m(2n+1)$$ as a solution. Another answer there asserted "there is no simple formula", which makes me wonder how (computationally) simple my proposed solution is.

With my proposed solution, if we know $n$ and $m$, we can easily compute $2^m(2n+1)$ (write the binary digits of $n$ followed by $1$ followed by $m$ zeroes). This takes $O(n+m)$ time.

Finding $m$ from the bits of $2^m 3^n$ amounts to finding the least significant bit (which can be computed by counting right bit shifts, leaving $3^n$ in memory). This takes $O(m)$ time.

However, we also need to find $n$, which might be more difficult. It would be possible to find $n$ by repeatedly dividing by $3$, but this seems wasteful. It requires $n$ division operations, each of which will take $O(n)$ time, so this is $O(n^2)$ time in total. [Actually, the after each iteration, the number of digits will decrease linearly, but this still results in $O(n^2)$ time.]

It seems like we should be able to exploit knowing the input is a power of $3$.

Answer 1

The obvious approach is:

(1) Compute an approximation to $\log_2(3^n)$. You can approximate it to within an additive error of 1 by counting the number of bits in the given binary representation, and to within an additive error of $\epsilon$ by additionally looking at the top $O(\log\frac{1}{\epsilon})$ bits of the input. It should suffice to choose a constant value of $\epsilon$, so that (after combining with the error in step (2)) the final result ends up within an additive error of $1/2$ of correct.

(2) Compute an approximation to $\log_2(3)$. I'm not familiar with the algorithms for this but I expect they take time polynomial in the number of bits of precision you need, and you only need $O(\log n)$ bits of precision.

(3) Divide the answer to (1) by the answer to (2), and round to the nearest integer.

So the first step takes linear time (in most models of computation although maybe not for some underpowered ones like single-head Turing machines) and the remaining steps should be polylogarithmic.

Answer 2

For any integer $n>0$, writing $3^n$ in binary requires exactly $L = \lceil \log_2(3^n)+1\rceil$ bits. Some elementary algebra implies that $$ \frac{L-2}{\log_2 3} \le n \le \frac{L-1}{\log_2 3}. $$ For any bit length $L\ge 1$, there is at most one integer in this range. Thus, given an integral power of $3$ that is $L$ bits long, the exponent must be the integer $$ n = \left\lfloor\frac{L-1}{\log_2 3}\right\rfloor. $$

Answer 3

Here is another approach. Given the low $k$ digits of $3^n$, you can learn $3^n \bmod 10^k$ and thus $3^n \bmod 5^k$. It looks like $3$ is a generator modulo $5^k$ (i.e., $3$ has order $\varphi(5^k)=5^{k-1} \times 4$).

Therefore, by using discrete log and Hensel lifting, I think you should be able to compute $n \bmod \varphi(5^k)$ from the low $k$ digits of $3^n$ very efficiently. In other words, you start by computing $n \bmod 4$ from the low digit of $3^n$, by taking the discrete log of $3^n \bmod 5$ to the base $3$, modulo $5$; this reveals $n \bmod 4$, and can be done in $O(1)$ time. Then, you find the discrete log of $3^n \bmod 25$ to the base $e$, modulo $25$; this reveals $n \bmod 20$, and can be done in $O(1)$ time (taking advantage of the knowledge of $n \bmod 4$, there are only $5$ possibilities you have to try). Iterate. At each step, you use the knowledge of $n \bmod \varphi(5^{k-1})$ to help you efficiently compute the discrete log of $3^n \bmod 5^k$, making use of the fact that there are only $5$ possible values for $n \bmod \varphi(5^k)$.

Now just let $k$ be large enough, and this reveals $n$.

You'll need to work out whether the running time is $O(n)$, but it looks to me like it might be. I suspect it's enough to let $k=O(n)$, and I suspect you can do each iteration in $O(1)$ time, for a total of $O(n)$ time.