It is well-known that the unit group of $\Bbb Z/2^k\Bbb Z$ is generated by $(-1)$ and $5$, and more precisely there is an isomorphism \begin{align*} (\Bbb Z/2\Bbb Z)\times(\Bbb Z/2^{k-2}\Bbb Z)&\longrightarrow (\Bbb Z/2^k\Bbb Z)^\times \\ (a,b)&\longmapsto (-1)^a\cdot 5^b. \end{align*} I would like to know if there is an efficient way to compute the inverse of this group isomorphism:
Given an odd number $1\le n< 2^k$, compute $0\le b< 2^{k-2}$ with $5^b\pm n\in 2^k\Bbb Z$.
By "efficient", I mean an algorithm that requires significantly less than $2^k$ steps, because with that many steps we can brute force the result. I was hoping that maybe there is an algorithm which is subexponential in $k$.
First you need to check when you have to switch the sign.
All the powers of $5$ are congruent to $1$ mod $4$, so given an $n \in (\Bbb Z/2^k \Bbb Z)^\times $, you get that $a=0$ if $n=1 \pmod 4$ and $a=1$ if $n = 3 \pmod 4$.
After switching the sign if necessary you are left with $n$ odd and congruent to $1$ mod $4$ and you want to write it as $5^b$ for some $b$.
Since $5$ has order $2^{k-2}$ mod $2^k$ for every $k \ge 2$, $5^{2^{k-3}} = 1 + 2^{k-1} \mod 2^k$ for $k \ge 3$.
Using this you can find this $b$ bit by bit by the following method :
For $2 \le l \le k$, let $b_l$ be the integer between $0$ and $2^{l-2}-1$ such that $n = 5^{b_l} \pmod {2^l}$, and let
Note that $b_2$ is always $0$.
Suppose you have computed $b_l$ and $5^{b_l} \pmod {2^k}$ for some $l < k$.
If $n = 5^{b_l} \pmod {2^{l+1}}$ then $b_{l+1} = b_l$.
If not then $n = 5^{b_l} + 2^l \pmod {2^{l+1}}$, and so $5^{b_l}5^{2^{l-2}} = 5^{b_l}(1+2^l) = 5^{b_l} + 2^l = n \pmod {2^{l+1}}$, therefore $b_{l+1} = b_l+2^{l-2}$. This allows you to compute every $b_l$ up to $l=k$, and your $b$ is $b_k$.
The operations needed to do this are computing the $5^{2^l} \pmod {2^k}$, so $k-2$ repeated squarings of $5$, and also computing the $5^{b_l} \pmod {2^k}$ so at most $k-2$ extra multiplications modulo $2^k$. The rest are bit operations, so all in all, the complexity is quasi-linear in $k$.