Can we compute $n$ from the bits of $3^n$ in $O(n)$ time? 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 &quot;there is no simple formula&quot;, 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$.
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.