2
$\begingroup$

$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}$?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How do I choose and/or find $v$? $\endgroup$ – desowin May 10 '16 at 6:21
  • $\begingroup$ Eep, I had variable-name drift. Fixed now. $\endgroup$ – Greg Martin May 10 '16 at 7:16
  • $\begingroup$ Is it possible to get solution that would work also for even values of $x$? $\endgroup$ – desowin May 10 '16 at 16:21
  • $\begingroup$ 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.) $\endgroup$ – Greg Martin May 10 '16 at 17:48
  • $\begingroup$ 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? $\endgroup$ – desowin May 11 '16 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.