Let $F$ be a $2$-adic field, i.e. a finite extension of the $2$-adic numbers $\mathbb{Q}_2$. Suppose that I have a quadratic extension $E = F(\sqrt{d})$ of $F$. Given a unit $\alpha \in \mathcal{O}_F^\times$, I would like to know the time complexity of an efficient algorithm to determine the following:
- Is $\alpha$ in the image of the norm map $N_{E/F}:E^\times \to F^\times$?
- If so, I want to find $\widetilde{\alpha}\in E^\times$ such that $N_{E/F}\widetilde{\alpha} \in \alpha F^{\times 2}$.
- Otherwise, I want to determine the maximum $i$ such that there are $x,y \in F^\times$ with $x^2 - dy^2 \equiv \alpha \pmod{\mathfrak{p}_F^i}$, and I want to find $x,y$ satisfying this condition.
In other words, I want either to obtain a norm preimage, or I want to "approximate" such an element as closely as possible.
I imagine one might approach this by some kind of "Hensel lifting", whereby we have solutions $x_i^2 - dy_i^2 \equiv \alpha \pmod{\mathfrak{p}_F^i}$ for $i=0,1,2,\ldots$, and construct $(x_{i+1},y_{i+1})$ inductively. Then at some point we either reach $i=2e_F + 1$, in which case we are done, or we stop being able to lift, which gives us Point (3) above. If the lifts can be done in $O(1)$ time, then this would be very good because the algorithm could be performed in $O(2e_F + 1)$ time. I don't know if such lifting is feasible, since the polynomial doesn't necessarily have a root, so the hypotheses of Hensel's lemma cannot be satisfied in general.
I know that MAGMA has a function called NormEquation, which addresses Points (1) and (2). Perhaps the algorithm of NormEquation can be adapted to my situation. I haven't been able to find out what it's doing under the hood though, so don't know. I also don't know its time complexity.
