How do I find the smallest positive integer $a$ for which $a^n \equiv x \pmod{2^w}$? $x$ is fixed odd positive integer value. $n$ and $w$ are fixed positive integer values. $a$ is positive integer value.
I am interested for $n=41$ and $w=160$, but would appreciate a general algorithm.
I know how to find any $a$ for which $a^n \equiv x \pmod{2^w}$. Algorithm requires $w$ steps:


*

*Let $a\leftarrow1$

*Iterate $i$ from 1 to $w-1$ and for each $i$ do:


*

*if $a^n \equiv x \mod(2^{i+1})$, do nothing.

*otherwise assign $a \leftarrow a+2^i$



Is this algorithm giving the smallest value $a$ for which $a^n \equiv x \pmod{2^w}$? How to find smallest $a$ for which $a^n \equiv x \pmod{2^w}$?

Note that here, the exponent $n$ is odd, while the order of every element modulo $2^w$ divides $\phi(2^w)=2^{w-1}$. Since $n$ and $2^{w-1}$ are relatively prime, the solution to $a^n=x\pmod{2^w}$ exists and is unique modulo $2^w$. So if you have a solution $a<2^w$, then it is indeed the smallest positive solution.
Another way of solving these problems is to find integers $y$ and $z$ for which $ny+2^{w-1}z=1$ (always possible when $n$ and $2^{w-1}$ are relatively prime), for then
$$
(x^y)^n = x^{ny} = x^{1-2^{w-1}z} = x\cdot(x^{2^{w-1}})^z \equiv x\cdot1^z = x\pmod{2^w}
$$
(where the congruence is due to Euler's theorem). Therefore $a\equiv x^y\pmod{2^w}$ is the solution. Both finding $y$ (from the extended Eucliden algorithm) and computing $x^y\pmod{2^w}$ are extremely fast when implemented correctly.
