# 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:

1. Let $a\leftarrow1$
2. 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.
• How do I choose and/or find $v$? – desowin May 10 '16 at 6:21
• Is it possible to get solution that would work also for even values of $x$? – desowin May 10 '16 at 16:21
• If $x$ is even then $a$ has to be even; if $x$ is not a multiple of $2^w$, then the power of $2$ dividing $a^n$ has to be exactly the same as the power of $2$ dividing $x$. So just factor out those powers of $2$ explicitly, and the problem reduces to a problem with odd numbers and a smaller value of $w$. (And if $x$ is a multiple of $2^w$, then you're just solving $a^n\equiv0\pmod{2^w}$ which is very easy.) – Greg Martin May 10 '16 at 17:48
• I have implemented it for even numbers and I am not getting correct results. If $x$ is even and $x/2$ is odd, I calculate $y$ for which $ny+2^{w-2}z=1$ and then I compute $a=2*((x/2)^y \pmod {2^{w-1}})$. But then $a^n \equiv (x*2^{40}) \pmod {2^{w+40}}$. $n$ and $w$ remains unmodified ($n=41$, $w=160$). What am I doing wrong? – desowin May 11 '16 at 17:33