For a given prime number $p$ (for simplicity, let's assume $p\neq 2$), the Teichmuller character is a character of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^{\times}$ that takes values in the roots of unity of $p$-adic integers. Does anyone know an efficient algorithm to compute the Teichmuller representatives of $\{1,2,\cdots,p-1 \}$ to some order?
More precisely, given an element $a \in \{1,2,\cdots,p-1 \}$, and an integer $n$, compute the Teichmuller representative up to order $p^n$!
It’s an easy algorithm, but fairly slowly convergent one, to start with $\beta\in(\Bbb Z/p\Bbb Z)^\times$, lift to any $b\in\Bbb Z$ that reduces to $\beta$, and successively raise to the $p$-th power. That is, go $b\mapsto b^p\mapsto(b^p)^p=b^{p^2}\mapsto b^{p^3}\mapsto\cdots$. You get one more place of $p$-adic accuracy each time you do it.
Why does it work? Because if $b\equiv b'\pmod{p^m}$, then $b^p\equiv{b'}^p\pmod{p^{m+1}}$, easily shown, though you should be careful if $p=2$ and $m$ is small.