Let $\mathbb{F}_q$ be the finite field with $q$ elements ($q=p^n$, $p$ is a prime). $\mathbb{F}_q$ can be regarded as a linear space over the field $\mathbb{Z}_p$ of dimension $n$. The question is:
How to choose the bases $(\epsilon_1,...,\epsilon_n)$ and $(\epsilon_1',...,\epsilon_n')$ of $\mathbb{F}_q/\mathbb{Z}_p$, such that for any $(i_1,...,i_n)\in\mathbb{Z}_p^n\backslash\{0\}$, we can quickly determine $(i_1',...,i_n')\in\mathbb{Z}_p^n\backslash\{0\}$, which satisfies $$(i_1\epsilon_1+\cdots+i_n\epsilon_n)(i_1'\epsilon_1'+\cdots+i_n'\epsilon_n')=1.$$
Well, I'm sure you know this, and probably it is not what you're looking for, but if you represent $\mathbf F_q$ as a quotient $\mathbf F_p[x]/(f)$ for some irreducible polynomial $f$ of degree $n$, then you can simply take $$ \varepsilon_k=\varepsilon_k'=x^k $$ for $k=0,\ldots,n-1$, and determine $i_0',\ldots,i_{n-1}'$ by applying the extended Euclidean algorithm to the polynomial $g=i_0+i_1x+\cdots+i_{n-1}x^{n-1}$ and $f$ in $\mathbf F_p[x]$. You find $a,b\in\mathbf F_p[x]$ such that $$ af+bg=1 $$ in $\mathbf F_p[x]$. In $\mathbf F_q$ this gives $bg=1$, i.e. $$ g^{-1}=i_0'+i_1'x+\cdots+i_{n-1}'x^{n-1}=b $$ in $\mathbf F_q$. This method is very fast, and you only need the Euclidean algorithm.